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_i^k$$$. What each of then is express

• $$$(\binom{n}{k}\mod p_1^{e_1})\mod p_2^{e_2})$$$ ... $$$\mod p_t^{e_t})$$$
• then strip off all the factors of pi from n!, k! and (n-k)! to compute $$$ n! * ModularInverse((n — k)!) * ModularInverse(k!) * (p_1)^{(total exponents of p_1 on numerator-total exponents of p_1 on frn denominator)}$$$
• details of this method for each $$$(\binom{n}{k}\mod p_1^{e_1})$$$ have been discussed on math.stackexchange (at least for cases when each $$$p_i$$$ is 32 bit integer.

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.me/blog/entry/65178 and https://codeforces.me/blog/entry/12878 .