263. Choose Mod Prime
A tournament organiser wants to know how many different squads of exactly r players can be picked from a pool of n distinct players. The order inside a squad does not matter, so the answer is the binomial coefficient C(n, r), which grows far too large to store directly.
Return C(n, r) modulo 1000000007 (a prime). Precompute factorials modulo the prime and use a modular inverse (Fermat's little theorem) instead of dividing. Aim for O(n) time and O(1) or O(n) extra space; take care that intermediate products do not overflow the integer type of your language.
Example 1
- Input:
- n = 7, r = 3
- Output:
- 35
- Explanation:
C(7,3) = 35, which is below the modulus so it is returned unchanged.
Example 2
- Input:
- n = 1000, r = 500
- Output:
- 159835829
- Explanation:
C(1000,500) is a 300-digit number; its remainder modulo 1000000007 is 159835829.
Constraints
0 ≤ r ≤ n ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + log MOD)
- Space
- O(1)