TCS Mockvita 1.0 2020: Lazy Student Problem (Python Solution)

Question Description:

There is a test of Algorithms. 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.

First line of each test case contains 3 integers separated by space denoting N, T, and M.

Output Format

For each test case, print a single integer.

If probability is p/q where p & q are co-prime, print (p*mulInv(q)) modulo 1000000007, where mulInv(x) is multiplicative inverse of x under modulo 1000000007.

Constraints:

0 < T <= 10000

0 < N, T <= 1000

0 <= M <= 1000

M,T <= N

Sample Input and Output:

Example 1

Input

1

4 2 1

Output

500000004

Solution in Python:

#importing necessary Modules

import math

arr =[]

test = int(input())

for i in range(test):

    

    #finding the probabilty

    l = list(map(int, input().split(' ')))

    N, T, M = l[0], l[1], l[2]

    c = math.factorial(N-M)

    b = math.factorial(T)

    a = math.factorial(N-M-T)

    prob = 1 - (c)/(b*c)

    

    #finding in fraction form

    p,q = (prob).as_integer_ratio()

    

    #finding multiplicative inverse

    m =1000000007

    y = pow(q,m-2,m)

    arr.append(y)

for i in range(test):

    print(arr[i])