Alice jogs everyday to keep herself fit and active. She noticed that she burns X calories when jogging the first kilometer, and for K > 1, jogging the K^{th} kilometer burns calories equivalent to the total number of calories burned while jogging the first K-1 kilometers.

What is the total number of calories that Alice burns after jogging for N kilometers? The answer can be very large, so report it modulo 10^{9} + 7 (1000000007).

------ Input Format ------

• The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains two space-separated integers N and X, as described in the problem statement.

------ Output Format ------

For each test case, output on a new line the total number of calories that Alice burns after jogging for N kilometers, modulo 10^{9} + 7.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{6}$
$1 ≤ X ≤ 100$

----- Sample Input 1 ------
3
1 2
2 1
12548 1

----- Sample Output 1 ------
2
2
588809226

----- explanation 1 ------
Test case $1$: Alice only jogs one kilometer, which burns $2$ calories since $X = 2$.

Test case $2$: Alice jogs two kilometers. The first burns $X = 1$ calorie, and the second also burns $1$ calorie since the total amount burnt before this is $1$ calorie. So, the total is $1 + 1 = 2$ calories burned.

见题面

见题面