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

• $$$m = as p_1^e_1.p_2^e_2...p_t_et$$$
• $$$\binom{n}{k}\mod m = \binom{n}{k}\mod p_1^e_1\mod p_2^e_1\mod p_t^e_t....\mod p_t^e_t$$$
• calculate C(n,k)mod p1_k = n! * reverse((n — k)!) * reverse(k!) which reverse(a) = power(a, mod — 2)

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