Eli- 1 started a part-time job handing out leaflets for N seconds. Eli- 1 wants to hand out as many leaflets as possible with her special ability, Cloning. Eli- gen can perform two kinds of actions below.

• Clone herself and generate Eli- (gen + 1) . (one Eli- gen (cloning) and one Eli- (gen + 1) (cloned) exist as a result of Eli-gen 's cloning.) This action takes gen $\times C ( C$ is a coefficient related to cloning. ) seconds.
• Hand out one leaflet. This action takes one second regardress of the generation ( =gen ).

They can not hand out leaflets while cloning. Given N and C , find the maximum number of leaflets Eli- 1 and her clones can hand out in total modulo 1000000007 (= 10^9 + 7).

Constraints

• $1 \leq Q \leq 100000 = 10^5$
• $1 \leq N_q \leq 100000 = 10^5$
• $1 \leq C_q \leq 20000 = 2 \times 10^4$

Input

The input is given from Standard Input in the following format:

Q
N_1 C_1
:
N_Q C_Q

The input consists of multiple test cases. On line 1 , Q that represents the number of test cases is given. Each test case is given on the next Q lines. For the test case $q ( 1 \leq q \leq Q ) , N_q$ and C_q are given separated by a single space. N_q and C_q represent the working time and the coefficient related to cloning for test case q respectively.

Output

For each test case, Print the maximum number of leaflets Eli- 1 and her clones can hand out modulo 1000000007 ( = 10^9 + 7 ).

Partial Scores

30 points will be awarded for passing the test set satisfying the condition: Q = 1 .

Another 270 points will be awarded for passing the test set without addtional constraints and you can get 300 points in total.

Examples

Input

2
20 8
20 12

Output

24
20

Input

1
20 3

Output

67

Input

1
200 1

Output

148322100

见题面

见题面