time-complexitycombinationsmodulusncr

nCr mod 10^9 + 7 for n<=10^9 and r <=1000

This may have been asked before but none of the answers I saw worked for me. I tried Lucas Theorem,Fermat's theorem but none of them worked. Is there an efficient way to find the value of:

nCr mod 10^9+7 where n<=10^9 and r<=1000

Any help will be very useful

Solution

  • n is large while r is small, you are better off compute nCr by n(n-1)...(n-r+1)/(1*2*...*r)

    You may need to find multiplicate inverse of 1, 2, ... r mod 10^9+7