Combinatorics nCr Modulo Prime Explained — Pascal Triangle, Factorial Inverse, Lucas Theorem [LC 62, Google, Meta]

Algorithm Statement#

Compute the binomial coefficient $\binom{n}{r} = \dfrac{n!}{r!(n-r)!}$, often modulo a prime $p$. Three regimes:

1. Small $n$ (up to a few thousand): Pascal's triangle in $O(n^2)$.
2. Medium $n$ (up to $10^6$) with prime modulus: precompute factorials and inverse factorials in $O(n)$, then answer each query in $O(1)$.
3. Huge $n$ (up to $10^{18}$) with small prime modulus: Lucas's theorem reduces to base-$p$ digits in $O(p + \log_p n)$.

Constraints typical in interviews:

• $1 \le n, r \le 10^6$ and $r \le n$.
• Modulus is usually $p = 10^9 + 7$ (prime).

Example:

n = 5, r = 2, p = 10^9 + 7
C(5, 2) = 5! / (2! * 3!) = 120 / 12 = 10
Output: 10

Why This Problem Matters#

Counting problems dominate the medium and hard tiers of every interview platform. LC 62 Unique Paths asks for $\binom{m+n-2}{m-1}$. LC 1922 Count Good Numbers asks for $4^{(n+1)/2} \cdot 5^{n/2}$ but extends to factorial-based variants. LC 1359 Count All Valid Pickup and Delivery Options is the central binomial coefficient times factorials. Google and Meta interviewers love these because they reward candidates who recognise the closed form, then compute it correctly under modular arithmetic without overflow.

The mistake I see most often: candidates know the formula but compute factorials naively, forget modular inverse, or use Fermat with a composite modulus. This blog cleans that up.

The Core Insight#

Three approaches scale differently:

Pascal's triangle. Use the recurrence $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ with base cases $\binom{n}{0} = \binom{n}{n} = 1$. Build a 2D DP table in $O(n^2)$ time and $O(n^2)$ or $O(n)$ space. Works for any modulus, prime or not.

Factorial precomputation. When the modulus $p$ is prime, compute fact[i] for $i \le N$ in $O(N)$. Then $\binom{n}{r} = n! \cdot (r!)^{-1} \cdot ((n-r)!)^{-1} \bmod p$. The two inverse factorials come from Fermat's little theorem: $(k!)^{-1} \equiv (k!)^{p-2} \pmod{p}$. A clever trick computes all inverse factorials in $O(N)$ by inverting only $N!$ and walking backwards: inv_fact[i] = inv_fact[i+1] * (i+1) mod p.

Lucas's theorem. For $n, r$ up to $10^{18}$ with a small prime $p$, write $n$ and $r$ in base $p$:

Then

Each $\binom{n_i}{r_i}$ has $n_i, r_i < p$, computable directly. Total time $O(p + \log_p n)$.

Why the inverse-factorial trick works. From $(i+1)! = (i+1) \cdot i!$ we get $(i!)^{-1} = (i+1) \cdot ((i+1)!)^{-1}$. Compute the largest inverse with one power call, then everything else with $N$ multiplications.

Visual Dry Run#

Compute $\binom{6}{2} \bmod (10^9 + 7)$ using factorial precomputation.

fact[0..6] = [1, 1, 2, 6, 24, 120, 720]
 
inv_fact[6] = power(720, MOD - 2, MOD)  → some big value F6
inv_fact[5] = inv_fact[6] * 6
inv_fact[4] = inv_fact[5] * 5
inv_fact[3] = inv_fact[4] * 4
inv_fact[2] = inv_fact[3] * 3
 
C(6, 2) = fact[6] * inv_fact[2] * inv_fact[4] mod p
        = 720 * (1/2) * (1/24) mod p
        = 720 / 48 = 15

Verify with Pascal: $\binom{6}{2} = \binom{5}{1} + \binom{5}{2} = 5 + 10 = 15$. Correct.

For Lucas, compute $\binom{1000}{300} \bmod 7$. Base 7: $1000 = 2626_7$ and $300 = 0606_7$.

Digits:  n = [2, 6, 2, 6]   r = [0, 6, 0, 6]
C(2,0) * C(6,6) * C(2,0) * C(6,6)
  = 1 * 1 * 1 * 1 = 1
 
So C(1000, 300) mod 7 = 1.

Solution (Optimal)#

Python — Factorial Precomputation#

MOD = 10**9 + 7
N = 10**6 + 5
 
fact = [1] * N
inv_fact = [1] * N
 
def precompute():
    for i in range(1, N):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)
    for i in range(N - 2, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
 
def nCr(n: int, r: int) -> int:
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD
 
precompute()

Complexity: $O(N)$ precompute, $O(1)$ per query, $O(N)$ memory.

Python — Lucas's Theorem#

def nCr_small(n: int, r: int, p: int) -> int:
    if r > n: return 0
    num = den = 1
    for i in range(r):
        num = num * ((n - i) % p) % p
        den = den * (i + 1) % p
    return num * pow(den, p - 2, p) % p
 
def lucas(n: int, r: int, p: int) -> int:
    result = 1
    while n > 0 or r > 0:
        ni, ri = n % p, r % p
        if ri > ni:
            return 0
        result = result * nCr_small(ni, ri, p) % p
        n //= p
        r //= p
    return result

Complexity: $O(p + \log_p n)$ per query.

JavaScript — Pascal's Triangle (small n)#

function pascalsTriangle(n) {
    const C = Array.from({ length: n + 1 }, (_, i) =>
        new Array(i + 1).fill(1n)
    );
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    return C;
}

JavaScript — Factorial Precomputation#

const MOD = 1_000_000_007n;
const N = 1_000_005;
const fact = new Array(N).fill(1n);
const invFact = new Array(N).fill(1n);
 
function power(a, n, m) {
    a %= m; let r = 1n;
    while (n > 0n) {
        if (n & 1n) r = r * a % m;
        a = a * a % m; n >>= 1n;
    }
    return r;
}
 
for (let i = 1; i < N; i++) fact[i] = fact[i - 1] * BigInt(i) % MOD;
invFact[N - 1] = power(fact[N - 1], MOD - 2n, MOD);
for (let i = N - 2; i >= 0; i--)
    invFact[i] = invFact[i + 1] * BigInt(i + 1) % MOD;
 
function nCr(n, r) {
    if (r < 0 || r > n) return 0n;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

Common Mistakes#

1. Computing factorials without modulo. $1000!$ overflows long before you finish. Apply % MOD after every multiplication.
2. Dividing instead of multiplying by inverse. Modular arithmetic does not support division. Use the inverse from Fermat or Extended Euclidean.
3. Wrong base case in Pascal. $\binom{n}{0} = \binom{n}{n} = 1$, and $\binom{n}{r} = 0$ when $r > n$ or $r < 0$.
4. Using Fermat with a composite modulus. Fermat requires $p$ prime. For composite, fall back to Lucas's generalisation or precompute via Pascal.
5. Building Pascal's triangle when $N$ is large. A $10^6 \times 10^6$ table is impossible; switch to factorial precomputation.
6. Lucas with $r > n$ at any digit. The base-$p$ digit comparison must short-circuit to 0 the moment some $r_i > n_i$.
7. JavaScript Number precision. All factorials must be BigInt; otherwise $\bmod (10^9 + 7)$ silently corrupts.

Interview Tips#

• Lead with the formula: "I will precompute factorials and inverse factorials in $O(N)$, then answer each $\binom{n}{r}$ in $O(1)$." This signals fluency.
• Mention the inverse-factorial trick: only one power call total, the rest is a backward sweep.
• If $n$ is large but the modulus is small, pivot to Lucas — never try to factorial $10^{18}$.
• For combinatorics on grids (paths) and lattices (Catalan), state the closed form before any code.

Follow-up Questions#

Q1: Compute $\binom{n}{r}$ when the modulus is not prime, like $m = 100$. A: Use Pascal's triangle, or factor $m$ into prime powers and apply Lucas's generalisation plus the Chinese Remainder Theorem.

Q2: Compute the central binomial coefficient $\binom{2n}{n}$ for $n = 10^6$. A: Same factorial precomputation; the answer is $\text{fact}[2n] \cdot \text{invfact}[n]^2 \bmod p$.

Q3: Compute Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$. A: Compute $\binom{2n}{n}$ as above, then multiply by the modular inverse of $n+1$.

Q4: Why is Lucas's theorem useful only for small primes? A: Lucas needs to compute $\binom{n_i}{r_i}$ for digits $n_i, r_i < p$. If $p$ is too big, the inner factorial precomputation does not fit in memory.

Key Takeaways#

• $\binom{n}{r}$ has three computational regimes: Pascal for tiny $n$, factorial precomputation for $n \le 10^6$, Lucas for $n$ up to $10^{18}$.
• Factorial precomputation runs $\binom{n}{r}$ queries in $O(1)$ after $O(N)$ setup, using one power call and a backward sweep for inverse factorials.
• Fermat's little theorem turns modular division into modular exponentiation: $(k!)^{-1} \equiv (k!)^{p-2} \pmod{p}$.
• Lucas's theorem factors the binomial coefficient over the base-$p$ digits — essential for giant arguments with a small prime modulus.
• Always guard the boundary cases r &lt; 0, $r > n$, and $\binom{n}{0} = 1$ before indexing into the factorial table.
• For composite moduli, fall back to Pascal's triangle or Lucas's generalisation paired with the Chinese Remainder Theorem.