# Combination

Time limit: 0.4s Memory limit: 128MB Input: combination.in Output: combination.out

You are given $q$ queries. For each of the queries you are given two integers, $n$ and $k$. Calculate $C_n^k \text{ mod } (10^9+7)$, where $C_n^k$ represents the number of ways to choose $k$ values from a set of $n$ ($n$ choose $k$).

## Input data

On the first line of the input file combination.in you have $q$, the number of queries. On each of the following $q$ lines you will have $n$ and $k$.

## Output data

For each of the $q$ questions we will print the answer in the output file combination.out. Because these numbers can be very large, you will need to print them modulo $10^9+7$.

## Constraints and clarifications

• $10^9 + 7$ is a prime number.
• $0 \leq q \leq 10^5$
• $0 \leq k \leq n \leq 10^5$
# Points Constraints
0 0 Example
1 20 $0 \leq n, q \leq 5 \cdot 10^3$
2 40 $0 \leq n, q \leq 10^4$

## Example

combination.in

11
7 5
35 20
85 40
67 40
44 7
76 69
60 35
44 43
28 20
44 13
93 17


combination.out

21
247943139
221670461
845448992
38320568
186189386
610920233
44
3108105
915526075
419070982


### Explanation

$C_7^5 \text{ mod } (10^9+7)= 21$.