Combinatorics & Modular Arithmetic

Counting problems — "how many ways to choose r items out of n?" — answer to the binomial coefficient nCr = n! / (r! * (n-r)!). The numbers blow past 64-bit integers almost immediately, so competitive and interview problems ask for the answer modulo a prime like 10^9 + 7. The trick is precomputing factorials mod that prime and replacing division with multiplication by a modular inverse.

The animation uses MOD = 13 (instead of 10^9 + 7) only so every number on screen stays one or two digits and you can check the arithmetic yourself.

Intuition

You cannot divide directly in modular arithmetic — 6 / 2 has no meaning once everything is a remainder mod 13. But division by x is the same as multiplying by x's inverse: the number that gives 1 when multiplied by x. Mod 13, the inverse of 2 is 7, because 2 * 7 = 14 = 1 (mod 13). So a / 2 becomes a * 7.

Where does the inverse come from? Fermat's little theorem says that for a prime p and any x not divisible by p, x^(p-1) = 1 (mod p). Divide both sides by x and you get x^(p-2) = inv(x). So one fast modular exponentiation — pow(x, MOD-2, MOD) in Python — hands you the inverse. Precompute factorials, invert two of them, multiply, and the count falls out.

Walk through it

Step through the animation on the right. The single row is the factorial table fact[0..5], built left to right. The i pointer scans it; the cell being read lights up, and the new cell fills in with fact[i-1] * i % 13.

Watch the table grow: fact[4] = fact[3] * 4 = 6 * 4 = 24, and 24 % 13 = 11, so the cell shows 11, not 24. Then fact[5] = 11 * 5 = 55, and 55 % 13 = 3. Once the table holds [1, 1, 2, 6, 11, 3], three pointers (n, r, n-r) mark the cells the formula reads: fact[5], fact[2], and fact[3]. The animation computes inv(fact[2]) = inv(2) = 7 and inv(fact[3]) = inv(6) = 11 via Fermat, then multiplies everything together: 3 * 7 * 11 % 13 = 231 % 13 = 10, which is exactly C(5, 2).

The code, line by line

def n_choose_r(n, r, MOD=13):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    # nCr = fact[n] / (fact[r] * fact[n-r])  (division = times inverse)
    inv_r = pow(fact[r], MOD - 2, MOD)       # Fermat
    inv_nr = pow(fact[n - r], MOD - 2, MOD)
    return fact[n] * inv_r % MOD * inv_nr % MOD

• fact = [1] * (n + 1) seeds fact[0] = 1 (the empty product) and reserves a slot for every factorial up to n.
• The loop fills fact[i] = fact[i-1] * i % MOD — multiply by the index, then immediately reduce so the value never overflows.
• inv_r and inv_nr are the modular inverses of fact[r] and fact[n-r], each computed by Fermat as pow(x, MOD-2, MOD). This is the step that replaces division.
• The final line multiplies fact[n] by both inverses, reducing mod MOD after each product, and returns the answer. The reductions keep every intermediate small.

Complexity

Building the factorial table once is O(n). After that each nCr costs two modular exponentiations, each O(log MOD) multiplications by fast exponentiation — effectively constant for a fixed modulus. If you answer many queries, precompute the table once and reuse it. You can even precompute an inverse-factorial table in O(n) so each query becomes truly O(1).

When to use / pitfalls

Practice