How to calculate modulo of a factorial?

Question

I am using C++ programming language. We are given 3 integers $x,y,z$ and I have to calculate :-

$(x +y +z)!/(x!*y!*z!) $ modulo $p$

where , $p=10^9+7$

Also , $0<=x,y,z<=10^5$

I tried many approaches but none of them worked. Fermat's theorem also does not work here :(

In C++,the maximum value an integer can have is 10^18.

Answer 1

This question was asked by me and I have found the answer.

You basically want to calculate $ k!/a!*b!*c!$ mod $p$

which can be re-written as :- $(k!$ mod $p)$ * $(1/a!)$mod $ p$ * $(1/b!)$mod $p$ * $(1/c!)$ mod $p$

To calculate m!%p:-

int fact[Maxn];

fact[0] = 1;

for(int i = 1; i < Maxn; i++)

{

fact[i] = 1LL * fact[i - 1] * i % Mod;

}

To calculate (1/x!) mod p :-

int ifact[Maxn];

ifact[0] = 1;

for(int i = 1; i < Maxn; i++)

{

ifact[i] = 1LL * ifact[i - 1] * inverse(i, Mod) % Mod;

}