Kyoto University Programming Contest 2016 - Handing out leaflets

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

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions: