Binomial Coefficient Modulo a Prime

Given two integers n and r with 0 <= r <= n, compute the binomial coefficient C(n, r) - the number of ways to choose r items from n distinct items - modulo the prime 1,000,000,007.

Input: A single line containing two space-separated integers n and r. Output: Print a single integer: C(n, r) mod (10^9 + 7).

1 <= n <= 10^6, 0 <= r <= n

Precomputing factorials ONCE (rather than for every query) is what makes this efficient at scale - this pattern (precompute shared structure once, answer each query cheaply) reappears throughout combinatorics-heavy competitive programming problems.

Compute 'n choose r' (the number of ways to pick r items from n) modulo a large prime, efficiently even for huge n. Brute force: Compute n! directly as an actual number and divide - this overflows almost immediately for n as small as 20, since factorials grow astronomically fast, making direct computation completely impractical for n up to 10^6. Optimised: Since the modulus is PRIME, Fermat's Little Theorem guarantees that x^(mod-2) is exactly x's modular inverse - this lets 'division' be simulated as multiplication by an inverse under the modulus, and precomputing all factorials ONCE (rather than per query) means each individual C(n,r) query only costs the two modular exponentiations for the inverses.

1. Precompute FACTORIALS 0! through n! modulo 1,000,000,007 in a single array upfront, rather than recomputing a fresh factorial per query. 2. Since the modulus is PRIME, use FERMAT'S LITTLE THEOREM: the modular inverse of x is x^(mod-2) mod (mod), computed via fast (binary) exponentiation. 3. C(n, r) = fact[n] * inverse(fact[r]) * inverse(fact[n-r]) mod (10^9 + 7).

Time: O(n) to precompute factorials once, plus O(log(mod)) per query for the modular inverse computations via fast exponentiation. Space: O(n), for the precomputed factorial array.

r=0 or r=n both yield C(n,r)=1. n can be as large as 10^6, so precompute factorials once in O(n) rather than multiplying r terms per query; the direct product n! would overflow any fixed-width type, so all arithmetic must be done modulo 10^9+7.

Be ready to explain WHY the modulus being PRIME specifically matters - Fermat's Little Theorem only applies to prime moduli; for a non-prime modulus, the more general Extended Euclidean Algorithm would be needed instead to find inverses.