Binomial coefficient modulo prime power I am trying to understand how to find binomial coefficients modulo a power of a prime. I am reading the paper by Andrew Granville for this. But I am unable to understand it completely. More specifically, I am unable to work out how each of $(N_j!)_p$ is computed efficiently. It would be really awesome if someone could show a small hand-worked example too - say $\binom{16}{5}$ mod $3^3$ or any other small example. Thanks in advance!
Edit Note: Earlier I had mentioned that I am unable to work out an example of the theorem by hand, but found out I was making a mistake. So have edited this question to understand how these coefficients are computed efficiently.
 A: Just to explain my understanding of theorem 2:
Note that the theorem starts by setting $p$, $u$ and $r$. So for now forget $q$:
If $p^{r}=2$ or $2r+1 = p$ or $2r+1=p^{2}$ then: $$(up!)_{p}  \equiv \pm \prod_{j=1}^{r}(jp!)_{p}^{\beta_{j}}( \mathrm{mod}\:p^{2r})$$ 
else : $$(up!)_{p}  \equiv \pm \prod_{j=1}^{r}(jp!)_{p}^{\beta_{j}}( \mathrm{mod}\:p^{2r+1})$$ 
Given that $ k p^{q+1} + a = (kp)p^{q} + a$ we can see that $$ \mathrm{if}\: x\equiv a \:\mathrm{mod}\: p^{q+1} \: \mathrm{then}\: x\equiv (\:a\%(p^{q})\:) \:\mathrm{mod}\: p^{q}$$
Now all we need is to set $r$ so that the $\mathrm{mod}$ holds for a number $t \geq  q$. Remember $t = 2r$ or $t = 2r+1$
Finally, compute the $\beta_{j}$ using the formula in the article, and the $(jp!)_{p}$ with $$ (jp!)_{p} = \frac{(jp)!}{j!p^{j}} \: \mathrm{for} \: 1\leq j \leq r$$
Note that the explanation for $\pm $ is not very clear, have a look at http://www.cecm.sfu.ca/organics/papers/granville/paper/binomial/html/node2.html for a better one ($\pm$ is $-$ only when $p=2$ and $[u/2] + \sum_{j=1}^{r}[j/2]\beta_{j}$ is odd)
For $(up!)_{p}$, the result $res$ will be the residue $\mathrm{mod} \: p^{t}$. Just take $res \% p^{q}$ and you are done.
