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

Output:

10
8
126