John wanted to buy gifts for some k children in his apartments on christmas.
He goes to the shop and the shopkeeper shows him n gifts.
How many ways John can choose k gifts from n total gifts ?.
Since answer could be large print the answer mod 1000000007

NOTE : ordering of the gifts do not matter
Different order of same set of gifts are considered same and should not be counted as different

Input
The first line of the input contains an integer t, number of test cases
next t lines follow with each line containing two integers (n and k) separated by space.

Output
For each test case print the answer in a new line.

Constraints
0 < n <= 100000
1< k <= 100000
1 < t <= 100

Example
Input:
1
5 1
Output:
5

Explanation
Example case .you can chose any one of the five gifts.so 5 ways

见题面

见题面