¿Cómo calcular el módulo de un factorial?

Question

Estoy utilizando el lenguaje de programación C++. Nos dan 3 enteros $x,y,z$ y tengo que calcular :-

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

donde , $p=10^9+7$

También , $0<=x,y,z<=10^5$

He intentado muchos enfoques pero ninguno ha funcionado. El teorema de Fermat tampoco funciona aquí :(

En C++, el valor máximo que puede tener un entero es 10^18.

Answer 1

Esta pregunta me la hice yo y he encontrado la respuesta.

Básicamente se quiere calcular $k!/a!*b!*c!$ mod $p$

que se puede reescribir como :- $(k!$ mod $p)$ * $(1/a!)$ mod $p$ * $(1/b!)$ mod $p$ * $(1/c!)$ mod $p$

Para calcular m!%p:-

int hecho[Maxn];

hecho[0] = 1;

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

{

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

}

Para calcular (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;

}