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