Factorial Modulo p

Computing $n!\mathrm{mod}m$ and $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathrm{mod}m$ — the case analysis depends entirely on how $m$ relates to $n$.

Case 1: $m$ prime, $n<m$ — the standard setup

Precompute factorials and inverse factorials once:

const int MOD = 1e9 + 7, N = 1e6 + 5;
long long fact[N], invFact[N];
 
void init() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = fact[i-1] * i % MOD;
    invFact[N-1] = powmod(fact[N-1], MOD - 2, MOD);
    for (int i = N-1; i > 0; i--) invFact[i-1] = invFact[i] * i % MOD;
}
long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
}

$O(N)$ preprocessing with one modular exponentiation, then $O(1)$ per binomial. This is the single most-used snippet in competitive programming.

Case 2: $m$ prime, $n\ge m$

$n!\equiv 0(\mathrm{mod}m)$ trivially (the product contains $m$). The interesting quantity is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathrm{mod}m$, which is not always 0.

Lucas’ theorem

Write $n$ and $k$ in base $p$: $n=\sum n_i{p}^i$, $k=\sum k_i{p}^i$. Then

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\equiv {\prod }_i\left(\genfrac{}{}{0ex}{}{n_i}{k_i}\right)(\mathrm{mod}p).$

long long lucas(long long n, long long k, long long p) {
    long long res = 1;
    while (n || k) {
        long long ni = n % p, ki = k % p;
        if (ki > ni) return 0;
        res = res * C(ni, ki) % p;                 // small binomial, precomputed
        n /= p; k /= p;
    }
    return res;
}

$O({\log }_{p}n)$ per query after precomputing factorials up to $p$. Practical for $p\le 10^6$.

Corollary (Kummer): $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is divisible by $p$ iff adding $k$ and $n-k$ in base $p$ produces a carry.

Case 3: $m=p^e$, a prime power

Use the generalised Lucas / Andrew Granville method:

1. Extract the power of $p$ separately with Legendre’s formula:
   $v_p\left(\left(\genfrac{}{}{0ex}{}{n}{k}\right)\right)=v_p(n!)-v_p(k!)-v_p((n-k)!),v_p(n!)={\sum }_{i\ge 1}\lfloor \frac{n}{p^i}\rfloor .$
2. Compute the $p$-free factorial $(n!{)}_p$ — the product of integers $\le n$ not divisible by $p$ — modulo $p^e$, recursively:
   $(n!{)}_p\equiv {\left({\prod }_{\begin{array}{c}1\le i\le p^e\\ p\nmid i\end{array}}i\right)}^{\lfloor n/p^e\rfloor }\cdot {\prod }_{\begin{array}{c}i\le n\mathrm{mod}{p}^e\\ p\nmid i\end{array}}i\cdot (\lfloor n/p\rfloor !{)}_p.$
3. Recombine.

Uses Wilson’s theorem to evaluate the block product. $O(p^e+{\log }_{p}n)$.

Case 4: $m$ arbitrary composite

Factor $m=\prod p_i^{e_i}$, apply case 3 to each prime power, and recombine with the CRT. Practical when every $p_i^{e_i}$ is small enough to precompute.

The decision table

$m$	$n$	Method	Cost
prime	$<m$	factorial + inverse factorial tables	$O(1)$ per query
prime	$\ge m$	Lucas	$O({\log }_{p}n)$
$p^e$	any	generalised Lucas (Granville)	$O(p^e+{\log }_{p}n)$
composite	any	factor + CRT	as above per factor
any	need $v_p$ only	Legendre’s formula	$O({\log }_{p}n)$
$10^9+7$, $n\le 10^7$	—	precompute; the common case	$O(1)$

Trailing zeros and divisibility

Number of trailing zeros of $n!$ = $v_5(n!)={\sum }_{i\ge 1}\lfloor n/5^i\rfloor$ — there are always more factors of 2 than of 5. See Trailing Zeroes.

In base $b$: factor $b=\prod q_i^{a_i}$ and take ${\min }_i\lfloor v_{q_i}(n!)/a_i\rfloor$.

Binomials without division

When the modulus is awkward, Pascal’s identity gives an $O(n^2)$ table with only additions:

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right).$

Valid for any modulus, including composites where inverses do not exist. Practical for $n\le 5000$.

Common pitfalls

Three recurring bugs

1. Not reducing before multiplying — fact[n] * invFact[k] can exceed long long if either is unreduced. Take % MOD after every multiplication.
2. $k>n$ or $k<0$ must return 0, not garbage from a negative index.
3. Assuming an inverse exists. With a composite modulus, powmod(x, MOD-2) is meaningless. Use the prime-power method.

See also: Lucas Theorem · Combinatorics · Wilson’s Theorem