[Seeking Help]Binomial Coefficients with Large Mod

[Seeking Help]Binomial Coefficients with Large Mod

I have been exploring the idea of computing Binomial Coefficients where , and are all 64 bit integers.ie is any integer rather than being a prime. I have found few solutions here where they first factorise into and then proceed for each in a manner similar to this method on math.stackexchange To elborate:

1. Express as ...
2. then strip off all the and its epponents from n!, k! and (n-k)!
3. and compute total exponents of in n! — total exponents of in (n-k)! — total exponents of in k!
4. if total exponents of in then answer is , if not proceed
5. You Repeat step 2-4 for all in .
6. and then result is
7. Details of this method for each have been discussed on math.stackexchange (at least for cases when each is 32 bit integer).

However among the solutions on yosupo none of the ones that I checked scale for large 64 bit . Just changing the data type won't fix as it overshoots memory even when the largest prime factor of is 32-bit. So 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 addresses either. My understanding is if they are implementing the algorithm similar to the discussion on math.stackexchange just scaling up datatype should work for the first part (ie is 64-bit but all of its prime factors are 32-bit). But to my surprise I found even in those cases it overshoots memory(or perhaps my edited code was buggy).

Any suggestions on how we can modify the code to scale to 64 bit for each of assuming that the largest prime factor of is within 32-bit(ie the fist part) I should call it out upfront that I have already gone through https://codeforces.com/blog/entry/65178 , https://codeforces.com/blog/entry/12878 , https://codeforces.com/blog/entry/55311 and https://codeforces.com/blog/entry/53039 .

To summarise all the ideas:

• Time per Query, Memory — initial answer by Aryaman Maithani on math.stackexchange
• Time per Query, Memory — proved using polynomial that in a subgroup of size product of only the constant term remains and other terms vanish . ie . — updated answer by Aryaman Maithani on math.stackexchange
• Time preprocessing, Time per Query, Memory — idea is to break each block of into sub-blocks of size each and then preprocess for each blocks of . This idea works because . The method is useful when we can't afford memory like the following two methods.
• Time preprocessing, Time per Query, Memory — Similar to Granville's idea. Basically the above 3 are also implementation of Granville's but with lesser degree of memorization that what Granville proposed.
• Time preprocessing, Time per Query, Memory — Similar to Min25's idea, it uses as Stirling number of the first kind and Lagrange's interpolation to implement it. There are few solutions on yosupo use Interpolation/NTT/FFT or some kind of domain transformation, I would put them in this category. SPyofcode might help us understand.

Where is the largest prime factor of and assuming it has or lesser