Binomial Coefficient mod p

Difficulty: Hard · Topic: Math for algorithms

Return C(n, r) mod p where p is prime. Division isn't allowed under a modulus, so divide by the denominator using its modular inverse: by Fermat's little theorem, x⁻¹ ≡ x^(p-2) (mod p). Compute the numerator and denominator mod p, then multiply by the inverse of the denominator.

Examples

ncr_mod(5, 2, 1000000007)
→ 10

ncr_mod(6, 3, 1000000007)
→ 20

Target complexity: time O(r + log p), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.