시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 101 76 69 77.528%

## 문제

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

## 예제 입력 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


## 출처

• 문제의 오타를 찾은 사람: songuno1