Skills101
← All coding problems

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 q lines: two integers n 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).

Loading editor…

Log in to run and submit your code — it's free.