Combinations

Taking $k$ elements out of a set of $n$ elements gives a $k$-combination.

For the set of the numbers from 1 to 5, the combinations are these:

• 1-combinations (1 element at a time): (1), (2), (3), (4), (5)
• 2-combinations (2 elements at a 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 at a 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 at a time): (1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 4, 5), (2, 3, 4, 5)
• 5-combination (all elements at once): (1, 2, 3, 4, 5)
• 0-combination (no element): ()

The number of $k$-combinations of a set of $n$ elements comes from this formula:

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

The list above gives $\binom{5}{0} = 1$, $\binom{5}{1} = 5$, $\binom{5}{2} = 10$, $\binom{5}{3} = 10$, $\binom{5}{4} = 5$, $\binom{5}{5} = 1$.

Given several $(n, k)$ pairs, compute $\binom{n}{k}$ for each one.

The first line has an integer $t$. Each of the next $t$ lines has two integers $n$ and $k$ separated by a space.

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

For each $(n, k)$ pair, print the number of $k$-combinations of a set of $n$ elements modulo $1000000007$ ($10^9 + 7$), one per line, in the order the pairs are given.