Codevita Previous Questions | LAZY STUDENT

LAZY STUDENT

LEVEL:Beginner

Description

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?

Input Format

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

Output Format

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.

Example 1:

Input

1
4 2 1

Output

500000004

Example 2:

Input

Output

280190717
280190717
120762861

Example 3:

Input

2
6 3 2
7 4 3

Output

280190717
280190717

Approach

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.

Beginner

LAZY STUDENT

LEVEL:Beginner

Description

Input Format

Output Format

Approach

Recommended Questions

Topic: Codevita Previous Questions

Beginner