I was calculating (n!/m!) mod 10^9 (not 10^9+7) . So I used following code to precalculate all factorials as: fact[0]=1; for(i=1;i<=n;i++) { fact[i] = (fact[i1]*i)%mod; //mod = 10^9 } 1<=m<=n<=1000 But somewhere in between it introduced 0 and that 0 propagates till n . So how to overcome such situation ?And yes it is working fine if mod = 10^9+7 . Sorry for bad language . In above code I am storing factorial of any n<=1000. And final result will be calculated directly by ans = (fact[n]/fact[m]) % mod . But my fact array working fine till fact[39] . i.e fact[1]=1 fact[2]=2 fact[3]=6 fact[4]=24 fact[5]=120 fact[6]=720 . . fact[39]=800000000 fact[40]=0 //because (fact[39]*40) % 10^9 = 0 and therefore fact[41]=fact[42]= .... fact[1000]=0 . So how to overcome such situation ?
This question is marked "community wiki".
asked 25 Oct '15, 10:22

What are the constraints on n and m? answered 25 Oct '15, 10:57

Can you explain your problem? 10^9+7 is a prime number. So upto (10^9+6)! There will be no term which will be divisible by 10^9+7. But for 10^9 which is not a prime number, it's prime factors will be covered by a sufficiently large n! which is 40 in this case. So you are getting zero after modulo. Also, (a+b)%m = a%m + b%m. This is not the case for a/b. i.e. a/b%m != a%m / b%m. So your approach is wrong. You need modular inverse. I am not sure how to find modular inverse for nonprime modulo. Sorry about that. answered 25 Oct '15, 15:10

Your "problem" actually leads to a quite efficient way. n!/m! will always be 0 if nm>=40. So in any case you can compute n!/m! in at most 39 steps. This will be fast enough for at least roughly $10^6$ testcases. If you have more you can in fact precompute the value for all 1<=m<=n<=1000. answered 25 Oct '15, 15:15

u are dealing with a special case where in n! mod m , m is a nonprime there are different algos available for this http://stackoverflow.com/questions/14802566/calculatingnmodmwhenmisnotprime this might help answered 25 Oct '15, 14:11
yess !! this is great . But I want to store (n! % 10^9) in advance so that I can use it in future .
(25 Oct '15, 14:30)

Your "problem" actually leads to a quite efficient way. n!/m! will always be 0 if nm>=40. So in any case you can compute n!/m! in at most 39 steps. This will be fast enough for at least roughly $10^6$ testcases. If you have more you can in fact precompute the value for all 1<=m<=n<=1000. answered 25 Oct '15, 15:15

if your modulo = 10^9 means you are just interested in the last 9 digits of your solution. answered 25 Oct '15, 21:47
