nCr mod prime power for large number How to calculate ${}^n\mathrm C_r \mod p^k$ for large $n$ and $r$?
For example ${}^{599999}\mathrm C_{50000}\mod 3^3$ or ${}^{599999}\mathrm C_{50000}\mod 3^5$ etc.
$1\le n,r<10^6$ and $2\le p\le 10^6$
 A: Here is a method that is hopefully efficient enough for your needs.
We note that
$$
  \binom{n}{r} = \frac{n(n-1)(n-2) \cdots (n-r+1)}{r(r-1)(r-2) \cdots 1}
$$
so we can calculate the binomial coefficient by multiplying together all of the terms in the numerator, and then dividing by each of the terms in the denominator. Of course multiplying all of the terms in the numerator gives us a very large integer, so since we are only interested in the value modulo $p^k$, we do all of the multiplications modulo $p^k$. (i.e. After we multiply by each term in the numerator, we take the answer mod $p^k$.)
But if we do the multiplication modulo $p^k$, we can no longer just divide by the terms in the denominator, we have to instead multiply by their multiplicative inverses. The problem now is that not all of the terms in the denominator have a multiplicative inverse modulo $p^k$ since some of them are divisible by $p$.
To remedy this, we first take out all of the factors of $p$ from each term in the numerator and denominator, and keep track of the total number of factors of $p$ in the numerator and denominator. We then know the exponent of the power of $p$ which divides the binomial coefficient: it is the difference between the exponent of the power of $p$ dividing the numerator, and the exponent of the power of $p$ dividing the denominator.
After we divide out all of the factors of $p$ from each term in the numerator and the denominator, we are left with terms which all have no factor of $p$. The new terms in the denominator are thus each relatively prime to $p^k$, and so we can find their multiplicative inverse modulo $p^k$ using the Extended Euclidean Algorithm.
So to get the answer that we want, we now multiply all of the new terms in the numerator (the ones without the factors of $p$), multiply by the multiplicative inverse of each of the new terms in the denominator (the ones without the factor of $p$), and finally multiply by the power of $p$ which divides the binomial coefficient. We then take this value modulo $p^k$.
A: We have
$$
\binom{599999}{50000}\equiv 0 \bmod 3^3
$$
because of Wolstenholme's congruence.
Edit: More generally we can just compute this by modular reduction and Pascal recursion, i.e., we do not have to compute the binomial coefficient first. Try a CSA. For example,
$$
\binom{599999}{50000}\equiv 0 \bmod 3^5
$$
