Your task is to calculate ~n~ binomial coefficients modulo ~10^9+7~.

A binomial coefficient ~{a \choose b}~ can be calculated using the formula ~\frac{a!}{b!(a-b)!}~. We assume that ~a~ and ~b~ are integers and ~0 \le b \le a~.

Input

• The first input line contains an integer ~n~: the number of calculations.

After this, there are ~n~ lines, each of which contains two integers ~a~ and ~b~.

Output

• Print each binomial coefficient modulo ~10^9+7~.

Constraints

• ~1 \le n \le 10^5~
• ~0 \le b \le a \le 10^6~

Example Input

3
5 3
8 1
9 5

Example Output

10
8
126