조합의 개수

원소가 $n$개인 집합에서 $k$개를 고른 것을 $k$-조합이라고 한다.

예를 들어 1부터 5까지의 수로 이루어진 집합에서는 다음과 같은 조합이 나온다.

• 1-조합(한 번에 1개를 고름): (1), (2), (3), (4), (5)
• 2-조합(한 번에 2개를 고름): (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)
• 3-조합(한 번에 3개를 고름): (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-조합(한 번에 4개를 고름): (1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 4, 5), (2, 3, 4, 5)
• 5-조합(모든 원소를 한 번에 고름): (1, 2, 3, 4, 5)
• 0-조합(아무 원소도 고르지 않음): ()

원소가 $n$개인 집합의 $k$-조합의 개수는 다음 식으로 구한다.

$\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}$

위 목록에서 보듯이 $\binom{5}{0} = 1$, $\binom{5}{1} = 5$, $\binom{5}{2} = 10$, $\binom{5}{3} = 10$, $\binom{5}{4} = 5$, $\binom{5}{5} = 1$이다.

여러 개의 $(n, k)$ 쌍이 주어질 때 각각에 대해 $\binom{n}{k}$를 계산하라.

첫째 줄에 정수 $t$가 주어진다. 이어지는 $t$개의 줄에는 공백으로 구분된 두 정수 $n$과 $k$가 주어진다.

• $1 \le t \le 1000$
• $1 \le n \le 1000$
• $0 \le k \le n$

각 $(n, k)$ 쌍에 대해 원소가 $n$개인 집합의 $k$-조합의 개수를 $1000000007$($10^9 + 7$)로 나눈 나머지를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.