Loading...
Loading...
Loading...
A placement cell has n students in a batch and must pick r of them for a company's interview panel. The order of the picked students does not matter.
The cell has q such questions. For each one, print the number of ways to choose r students from n, modulo 10^9 + 7. If r is larger than n, there is no way to do it, so print 0.
Example 1
Input
3 5 2 4 4 3 5
Output
10 1 0
From 5 students, 10 pairs. Choosing all 4 of 4 is 1 way. 5 from 3 is impossible.
Example 2
Input
1 67 33
Output
34643904
The exact answer is about 1.4 × 10^19, too big even for a long.
Try the problem first. Open one hint at a time.
The count is n! / (r! × (n - r)!). With many questions, compute every factorial up to the largest n once.
You cannot divide after taking % MOD. Instead, multiply by the modular inverse: the number y with x × y % MOD = 1.
Because 10^9 + 7 is prime, the inverse of x is x to the power (10^9 + 5), modulo 10^9 + 7. Use fast power.
Find the inverse of the largest factorial once, then go down: inverse of (i - 1)! = inverse of i! × i.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor