AKVRRI02 - Joey is Confused 300 points

no tags 

So many girls are in love with Joey. He wants to make all of them happy by taking them out for a movie tonight, but unfortunately he has only "K" movie tickets. So he wants to consider all the possible combinations of "K" girls. He just asked you how many different combinations of "K" girls he can make out of "N" girls, can you tell this to him? You know that sometimes this number can be huge, so you should tell him answer modulo 1,000,000,007.

Input

First line contains an integer "T", the number of test cases. Each of the next "T" lines will contain only 2 integers "N" and "K".

Output

For each test case print a single number modulo 1,000,000,007 that is the number of possible combinations of "K" girls out of "N" girls.

Constraints

1 <= T <= 10^5

1 <= N <= 1000

0 <= K <= N

Example

Input:
5
1 0
2 1
5 3
6 6
35 13

Output:
1
2
10
1
476337793


Added by:Ankit Kumar Vats
Date:2013-07-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self