Counting stars

4.5

6 votes
Approved, Combinatorics, Easy, Math, Ready, Recruit, approved
Problem

There are N stars in the sky. A manual attempt at counting yielded K stars. It is possible that the same star may have been counted more than once. You need to determine the probability that any star may have been counted more than once. Probability can be represented as a rational number PQ. If Q is not divisible by 109+7 there is a unique integer x0x<109+7 where PQx % (109+7). Calculate value of this integer x.

Input Format:
First line of input consists of a single integer T denoting number of test cases.
Following T lines contain two space separated integers denoting N and K.

Output Format:
Print the answer to each test case in a new line.

Input Constraints:
1T10
1N,K100000

Sample Input
1
3 3
Sample Output
300000003
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are 3 stars in the sky. Let's call them A, B and C.
Following are the different ways that Micro could have counted the stars.
(A,A,A)
(B,B,B)
(C,C,C)
(A,A,B)
(A,B,B)
(A,A,C)
(A,C,C)
(B,B,C)
(B,C,C)
(A,B,C)
So, clearly there are 9 out of 10 ways, in which Micro counted any star more than once. So, probability is 910, and 9(10×300000003)%109+7. So x=300000003.

Editor Image

?