Hi, I was solving POP1 but can't get it to pass under the time limit.

Things I've tried.

1. For detecting pop numbers, I simply brute force.
2. For checking primes, I maintain an array of primes till 2e7 and after that apply Miller-Rabbin.

Here is my code.

I want to find nCr(n choose r, if you will) modulo a prime. The trouble is that all the numbers i.e. n, r and prime are large and are of the order of 10^9.

One method I could come up with is computing each of the three factorials individually(using FFT and multipoint evaluation) but that seems too tedious. It may also timeout.

Is there anything else I can do ?