Combination

Task

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$

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