nCr Modulo 10^9+7
mediumMath & Number Theory+20 XPTime limit 3s
A coaching centre wants to know in how many ways it can choose r students out of n for a team — the binomial coefficient nCr = n! / (r! · (n−r)!). The numbers get huge, so print each answer modulo 1000000007 (10⁹ + 7, a prime). If r > n there is no way, so print 0.
Input:
- line 1:
q - next
qlines: two integersn r
Output: q lines — nCr mod 1000000007.
Constraints: 1 ≤ q ≤ 10⁵, 0 ≤ n, r ≤ 10⁶.
Think about it: precompute fact[i] up to the largest n, and the inverse factorials invFact[i]. Because the modulus is prime, the inverse of x is x^(p−2) mod p (Fermat). Then each query is fact[n] · invFact[r] · invFact[n−r], all mod p — O(1) per query.
Sample input 1
3 5 2 10 0 3 5
Sample output 1
10 1 0
Sample input 2
1 1000000 500000
Sample output 2
996692777
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).