When we have a set of n elements from which we take k elements, we have a combination.</p>

For example, if we have a set with the numbers from 1 to 5, we have the following different combinations:

• 1-combinations (1 element from the set each time): (1), (2), (3), (4), (5)
• 2-combinations (2 elements from the set each time): (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5).
• 3-combinations (3 elements from the set each time): (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5), 
• 4-combinations (4 elements from the set each time): (1, 2, 3, 4), (1, 3, 4, 5), (1, 2, 4, 5), (1, 2, 3, 5), (2, 3, 4, 5)
• 5-combination (all the elements at once): (1, 2, 3, 4, 5)
• 0-combination (no element): ()

The following formula will give us the number of k-combinations of n elements:

[{n \choose k} = \frac{n (n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}]

As we saw in the list before

• (5 over 0) = 1
• (5 over 1) = 5
• (5 over 2) = 10
• (5 over 3) = 10
• (5 over 4) = 5
• (5 over 5) = 1 

Your task is to compute several (n over k) operations.

입력 형식

A line with an integer t. The following t lines will contain 2 integers each separated by spaces. The first value will be n and second k.</p>

• 1 ≤ t ≤ 1000
• 1 ≤ n ≤ 1000
• 0 ≤ k ≤ n

For each (n k) pair. Compute the number of k-combinations of a set of size n. Compute the results modulo 1000000007 (10^9 + 7).

예제 입력 1

6
5 0
5 1
5 2
5 3
5 4
5 5

예제 출력 1

1
5
10
10
5
1

예제 입력 2

3
123 54
7 4
20 10

예제 출력 2

757228090
35
184756