nCr mod p for many queries

medium ~20 min

Implement a class Binomial(max_n, p=MOD) where MOD = 1_000_000_007 (define it in your solution). p is a prime larger than max_n.

The constructor precomputes whatever it needs in O(max_n) time (plus one O(log p) inverse).
.ncr(n, r) returns C(n, r) mod p in O(1) for 0 <= n <= max_n. Return 0 when r < 0 or r > n.

b = Binomial(10)
b.ncr(5, 2)    # 10
b.ncr(10, 0)   # 1
b.ncr(4, 5)    # 0
b.ncr(4, -1)   # 0
Binomial(10, 13).ncr(10, 5)   # 5   (252 mod 13)

Constraints: 0 <= max_n <= 10^6; the tests build a table for max_n = 10^6 and then ask 200,000 queries.

Computing a fresh modular inverse for every index (or every query) is far too slow.

Show hint

C(n, r) = n! / (r! (n-r)!), so tables of factorials and of their inverses mod p answer each query with two multiplications. You only need one modular inverse (via Fermat's little theorem): the rest of the inverse table follows by walking down, since 1/(i-1)! = i / i!.

Topic: Modular arithmetic. Fast exponentiation, Fermat inverses, nCr mod p with factorial tables.