# Calculating $\binom{n}{r} \bmod\; p$ where $p$ is prime and as large as $1000000007$

I am trying to calculate $\binom{n}{r}$ modulo $1000000007$. I have read here about Lucas' Theorem but it seems to work for small values of $p$. Here $p = 1000000007$. Is there a way this can be solved? Thank you.

-
I take it by the use of "%" that you mean $\bmod \;p$? – amWhy Dec 3 '12 at 14:33
Yes, I mean modulo p. – Rishi Dec 3 '12 at 14:39
Since I see 1000000007 here I think this is programming contest problem. You'd better look at this stackoverflow.com/questions/10118137/… – Norbert Dec 3 '12 at 15:08
Yes, this is from a contest. I have the idea how to solve the problem, but this comes in the way to solve it. – Rishi Dec 3 '12 at 17:34

By Legendre formula $$\Large n!=\prod\limits_{p\in P,p\leq n} p^{\left(\sum\limits_{1\leq k\leq \log_p n}\left\lfloor\frac{n}{p^k}\right\rfloor\right)}$$ where $P$ is the set of prime numbers. So to solve the problem you need to precompute primes less than $n$, and then optimize computation of formula given above.