Array ( [0] => [1] => questions [2] => Basic [3] => LAZY-STUDENT )
There is a test of Algorithms. The teacher provides a question bank consisting of N questions and guarantees all the questions in the test will be from this question bank. Due to lack of time and his laziness, Codu could only practice M questions. There are T questions in a question paper selected randomly. Passing criteria is solving at least 1 of the T problems. Codu can't solve the question he didn't practice. What is the probability that Codu will pass the test?
First-line contains single integer T denoting the number of test cases.
The first line of each test case contains 3 integers separated by space denoting N, T, and M.
Constraints
0 < T <= 10000
0 < N, T <= 1000
0 <= M <= 1000
M,T <= N
For each test case, print a single integer.
If the probability is p/q where p & q are co-prime, print (p*mulInv(q)) modulo 1000000007, where mulInv(x) is the multiplicative inverse of x under modulo 1000000007.
1 4 2 1
500000004
3 10 3 2 8 3 1 9 5 4
280190717 280190717 120762861
2 6 3 2 7 4 3
280190717 280190717
Login to see Discussion
The formula for the probability that Codu will pass the examination is (1 - ( (N-M)! / (T! * (N-M)! ) )). After calculating the probability, convert the probability into p/q form and then find the multiplicative inverse index under modulo 1000000007.
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution