$\binom{n}{k}$ modulo prime power for large $n$ and small $k$ I have to compute several value of $\binom{n}{k}$ mod $p^a$ for prime $p$ over a range of $k$, where $n$ is large and fixed, and $k$ is small and dynamic.
Is there a way to speed the process up? If I use iterative identities, I often run into coprimality issues that prevent me from inverting the denominators.
I've found Granville's method (generalized Lucas) but it is too slow to compute it for each binomial.
Bounds: $n$ around $10^8$ or so. $k$ at most around $10^5$. Modulus can be a prime power up to $10^8$ (roughly).
 A: Try using $\binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1}$. To avoid issues with dividing by $k$, in case $k$ has an exponent of $p$, just keep track of the exponent of $p$ separately. For example have a cumulative tracker called pow. Now, if $p \mid n$, then replace $n$ with $n/p$ in the numerator, and increment pow by 1. Similarly, if $p \mid k$, then replace $k$ with $k/p$ in the denominator and decrement pow by 1. At the end, multiply what you have by $p^\text{pow}$. Some pseudocode:
function binommod(n, k, p, a): [Returns an array of nCi mod p^a for i ranging from 0 to k]
    answers = an array of k+1 integers.
    currentans = 1
    pow = 0
    answers[0] = 1
    for i in [1, k]:
        numer = n - i + 1
        denom = i
        while p | numer:
            numer = numer / p
            pow = pow + 1
        while p | denom:
            denom = denom / p
            pow = pow - 1
        currentans = currentans * numer / denom (mod p^a) [You should have an algorithm for this already, provided p does not divide k]
        answers[i] = currentans * p^pow (mod p^a)
    return answers

