# How to calculate binomial coefficient C(n, r) modulo some prime power?

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.