시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 32 26 24 82.759%

문제

When we have a set of n elements from which we take k elements, we have a combination.

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.

  • 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).

예제 입력

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

예제 출력

1
5
10
10
5
1

예제 입력 2

3
123 54
7 4
20 10

예제 출력 2

757228090
35
184756

힌트