407336: GYM102767 B 2024

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)$$$.

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) $$$.

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)$$$.

3
1 4
2 3
3 5

4
9
35

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.