Introduction

Computing n choose k mod p efficiently depends on what is large and what is fixed. If n is huge but p is a prime and relatively small, Lucas's theorem is often the key tool. If n is only moderately large and you need many queries under the same prime modulus, factorial precomputation with modular inverses is usually the fastest practical approach.

The Basic Formula Is Not Enough

The direct combinatorial formula is:

C(n, k) = n! / (k! (n-k)!)

But under modular arithmetic you cannot divide directly. For prime p, the usual trick is to replace division with multiplication by modular inverses.

That gives:

C(n, k) mod p = fact[n] * inv_fact[k] * inv_fact[n-k] mod p

where the inverse values are computed modulo p.

Fast Method for Moderate n

When n is not astronomically large and p is prime, precompute factorials and inverse factorials:

1def mod_pow(a, e, mod):
2    result = 1
3    while e > 0:
4        if e & 1:
5            result = (result * a) % mod
6        a = (a * a) % mod
7        e >>= 1
8    return result
9
10
11def build_factorials(limit, mod):
12    fact = [1] * (limit + 1)
13    inv_fact = [1] * (limit + 1)
14
15    for i in range(1, limit + 1):
16        fact[i] = (fact[i - 1] * i) % mod
17
18    inv_fact[limit] = mod_pow(fact[limit], mod - 2, mod)
19
20    for i in range(limit, 0, -1):
21        inv_fact[i - 1] = (inv_fact[i] * i) % mod
22
23    return fact, inv_fact
24
25
26def n_choose_k_mod(n, k, mod, fact, inv_fact):
27    if k < 0 or k > n:
28        return 0
29    return fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod

This gives O(1) query time after O(n) preprocessing.

Lucas's Theorem for Huge n

If n is very large relative to p, Lucas's theorem helps by decomposing the problem into base-p digits:

C(n, k) mod p = product of C(n_i, k_i) mod p

where n_i and k_i are the digits of n and k in base p.

That means the giant problem becomes a product of much smaller binomial problems.

Example implementation:

1def lucas(n, k, p, fact, inv_fact):
2    if k == 0:
3        return 1
4
5    ni = n % p
6    ki = k % p
7
8    if ki > ni:
9        return 0
10
11    small = n_choose_k_mod(ni, ki, p, fact, inv_fact)
12    return (small * lucas(n // p, k // p, p, fact, inv_fact)) % p
13
14
15p = 7
16fact, inv_fact = build_factorials(p - 1, p)
17print(lucas(1000, 300, p, fact, inv_fact))

This is the standard fast answer when p is prime and n is too large for full factorial precomputation up to n.

Use Symmetry Too

Always reduce k with:

k = min(k, n-k)

That small step can significantly reduce work in algorithms that iterate over k or depend on the smaller side of the binomial coefficient.

Even when using Lucas's theorem, this symmetry can still simplify the subproblems you solve.

Common Pitfalls

• Trying to divide directly under modulo arithmetic instead of using modular inverses.
• Forgetting that the common inverse trick depends on p being prime.
• Precomputing factorials up to a gigantic n when Lucas's theorem is the right tool.
• Ignoring the k > n case, which should return 0.
• Using a method for prime moduli on a composite modulus without rethinking the number theory.

Summary

• For prime p and moderate n, factorial plus inverse-factorial precomputation is the standard fast method.
• For huge n, Lucas's theorem is the usual answer.
• Modular inverses replace division in the binomial formula.
• Reducing k to min(k, n-k) is a simple but useful optimization.
• The right algorithm depends on the size of n, the size of p, and whether p is prime.