How to calculate C(n, r) modulo m, m is of the form p^a, where p is prime.
Here C(n, r) means n choose r. The range of n and r is large (of the order of 10^18) so it cannot be solved by calculating the power of primes. Also m is less than 10^6. I tried reading the generalization of Lucas Theorem, but could not understand it. It will be really helpful if someone could explain a feasible method to solve the problem.
Till now I have tried this. I stored every prime number from 1 to n in an array p. Then calculated the power of pi 1<=i<=|p| in n! and added it to arr[i]. Similarly calculated the power of pi 1 <=i<=|p| from 1 to r in r! and subtracted it from arr[i]. Same for (n-r)!. Then multiplied (p[i]^arr[i])%(p^a) to answer while taking modulo. But this runs in O(n) which is too slow for the above mentioned constraints.
There is a citation in the wikipedia page of Lucas's theorem for generalized form of Lucas's theorem but the link is not working.