Binomial Coefficient

Compute n choose k modulo 10^9+7 efficiently without overflow.

modular-arithmetic combinatorics dynamic-programming precomputation

Write a function `binomial_coefficient(n: int, k: int) -> int` that returns the value of the binomial coefficient C(n, k) modulo 1_000_000_007 (10^9 + 7). The binomial coefficient is defined as C(n, k) = n! / (k! * (n-k)!) for 0 <= k <= n. The result must be an integer modulo the given prime.

Your implementation must handle n up to 100,000 and multiple calls efficiently within a single invocation. It is recommended to precompute factorials and inverse factorials modulo the prime, but the test harness will call the function repeatedly. Ensure your function works within reasonable time and memory limits.

Constraints

0 <= k <= n <= 100_000. The result must be modulo 1_000_000_007. The function will be called up to 10,000 times in a single run. Time limit: 2 seconds, Memory limit: 256 MB. You may use Python's built-in pow for modular inverse.

Example

>>> binomial_coefficient(5, 2)
10
>>> binomial_coefficient(5, 0)
1
>>> binomial_coefficient(5, 5)
1
>>> binomial_coefficient(10, 3)
120
>>> binomial_coefficient(100000, 50000)
149033233

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use Fermat's little theorem to compute modular inverses: a^(MOD-2) mod MOD.

Precompute factorials up to the maximum n (100,000) once and reuse them.

Remember C(n, k) = C(n, n-k) to reduce computation for k > n//2.

If n=0 and k=0, return 1.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.