I have been exploring the idea of computing Binomial Coefficients $$$\binom{n}{k}\mod m$$$ where $$$n$$$,$$$k$$$ and $$$m$$$ are all 64 bit integers.ie $$$m$$$ is any integer rather than being a prime. I have found few solutions here where they first factorise and then proceed for each $$$p^k$$$. However almost none of them scale for large 64 bit $$$m$$$. Just changing the data type wont fix as it overshoots memory. How should I modify them to scale to 64 bit for each of $$$n,k,m$$$ ? Or if any one have already written a library which scales to 64 bit for each of $$$n, k, m$$$ please do share.

There can be two parts to the problem

• m is 64-bit but all of its prime factors are 32-bit
• m is 64-bit and one of its prime factor is 64-bit

None of the solutions submitted on yosupo implements either.

I should call it out upfront that I have already gone through https://codeforces.net/blog/entry/65178 and https://codeforces.net/blog/entry/12878 .