Binomial Coefficient Modulo a Prime
Advanced
Return the binomial coefficient C(n, k) (the number of ways to choose k items out of n) modulo 10**9 + 7. It is 0 when k < 0 or k > n.
For n = 5 and k = 2 the answer is 10.
The starter code builds the exact number, which becomes enormous. It is correct but too slow when k is large.
Examples
Example 1
Input:
binomial_mod(5, 2)
Output:
10
Example 2
Input:
binomial_mod(4, 5)
Output:
0
Constraints
0 <= n <= 10**9-1 <= k <= nandmin(k, n - k) <= 10**6
Theory
Go to TheoryKeywords
dsa-sheetmathscounting-and-digits
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.