B. 2024
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We have a sequence of $$$n$$$ integers and a number $$$x$$$.

Initially $$$a_1 = a_2 = a_3 = \ldots = a_n = x$$$.

In one move, you can choose any index $$$i$$$ if and only if $$$a_i = a_{i+1}$$$ and $$$1 \le i \le n-1$$$ and perform a operation : $$$ a_i = a_i + a_{i+1} $$$ and $$$a_{i+1} = x$$$.

For example - $$$n = 3, x = 5$$$, Initially sequence is $$$a = [5,5,5]$$$,

choose $$$i = 1$$$, array will change to $$$a = [10,5,5]$$$.

choose $$$i = 2$$$, array will change to $$$a = [10,10,5]$$$.

choose $$$i = 1$$$, array will change to $$$a = [20,5,5]$$$.

choose $$$i = 2$$$, array will change to $$$a = [20,10,5]$$$.You cannot choose any index now.

You can perform any number of moves, and any index can be chosen any number of times (including zero). Your task is to find out the maximum possible sum of array we can obtain.

As the answer can be rather large, print the remainder after dividing it by $$$1000000007 (10^9 + 7)$$$.

Input

The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each query contains two integers - $$$n (1\le n \le 10^9)$$$ : total numbers in the sequence and $$$x (1\le x \le 10^9) $$$.

Output

For each test from the input print the maximum possible sum we can obtain by performing moves any number of time modulo $$$1000000007 (10^9 + 7)$$$.

Example
Input
3
1 4
2 3
3 5
Output
4
9
35
Note

In the first query — Initially $$$a = [4]$$$. we cannot perform any moves.

In the second query — Initially $$$a = [3,3]$$$.

choose $$$i = 1$$$, array will change to $$$a = [6,3]$$$. now we cannot perform any move. So maximum sum is $$$9$$$.

Last query is discussed in Problem Statement.