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.
Calculating $\binom{n}{r} \bmod\; p$ where $p$ is prime and as large as $1000000007$
2
$\begingroup$
combinatorics
permutations
-
0I take it by the use of "%" that you mean $\bmod \;p$? – 2012-12-03
-
0Yes, I mean modulo p. – 2012-12-03
-
2Since I see 1000000007 here I think this is programming contest problem. You'd better look at this http://stackoverflow.com/questions/10118137/fast-n-choose-k-mod-p-for-large-n – 2012-12-03
-
0Yes, this is from a contest. I have the idea how to solve the problem, but this comes in the way to solve it. – 2012-12-03