There are $q$ queries, each of the form $(n, k)$, calculate the binomial coefficient: $${n\choose k}=\frac{n!}{k!(n-k)!}$$
### Input
- The first line contains an integer $q$.
- Each line in the next $q$ lines contains 2 integers $n, k$.
### Output
- Print each binominal coefficient modulo $10^9+7$.
### Constraints
- $1 \le q \le 10^6$.
- $1 \le k \le n \le 10^6$.
### Example
Input:
```
2
6 4
5 3
```
Output:
```
15
10
```
