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)! and 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. My understanding is if they are implementing the algorithm similar to the discussion on math.stackexchange just scaling up datatype should scale for the first part (ie m is 64-bit but all of its prime factors are 32-bit). But I found even in those cases it overshoots memory.

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