How to calculate ((a+b)!/a!b!) mod p
I am looking for an efficient way to calculate ((a+b)!/a!b!) mod p. p is prime.
for example if a=10 and b=7 and p=3 then we need to find (17!/10!.7!) mod 3
The above can be reduced to (126.96.36.199.13.12.11/188.8.131.52.3.2.1) mod 3
The problem i am facing is a and b can have a very high value i.e 1<=a<=1000000000 and 1<=b<=1000000000 and value of p is say 531169.
So how would i programmatically calculate the value, since intermediary calculations might overflow an int variable.
Since (a/b)mod p != ((a%p)/(b%p)) mod p. Right ?
Is there a trick involved ?
Thanks for your patience