Description

There are $T$ queries. In each query, you are given two positive integers $n, l$.

You need to construct a positive integer sequence $a$ of length $l$ (indexed from $1$ to $l$), such that for all $i \in [1, l]$, we have $a_i \in [1, n]$.

Find the maximum value of:

To avoid the answer being too large, for each query, you only need to output this maximum value modulo $10^9+7$.

Input Format

The first line contains an integer $T$, representing the number of test cases.

Then from line $2$ to line $T+1$, each line contains two integers $n, l$, representing the maximum possible value of $a_i$ and the length of $a$, respectively.

Output Format

Output $T$ lines, each containing one integer: the answer for the corresponding query modulo $10^9+7$.

1
2 3

6

2
114 514
1919 180

8388223
16580700

Hint

Sample Explanation #1
When $n=2, l=3$, if $a$ is any permutation of $\{1,2,1\}$, the maximum value can be achieved, which is $(1\oplus2)+(1\oplus1)+(2\oplus1)=6$. It is easy to prove that the expression reaches its maximum in this case.

Constraints | Test Point ID | $T\le$ | $n\le$ | $l\le$ | | :----------: | :----------: | :----------: | :----------: | | $1\sim5$ | $1$ | $10$ | $5$ | | $6$ | $5\times 10^5$ | $10^{12}$ | $2$ | | $7$ | $5\times 10^5$ | $10^{12}$ | $3$ | | $8\sim10$ | $5\times 10^5$ | $10^{12}$ | $10^5$ |

For $100\%$ of the data, $1\le T\le 5\times10^5$, $1\le n\le 10^{12}$, $2\le l \le 10^5$.

Hints

1. "$\oplus$" is the bitwise XOR operator. If you do not know what bitwise XOR is, you can refer to here.
2. Modulo is an operation. Taking $a$ modulo $b$ means assigning $a$ to the remainder when $a$ is divided by $b$.
   In C++ / Python, the modulo operator is %, and in Pascal it is mod.
3. $\sum$ is the summation symbol. If you do not know what $\sum$ means, you can refer to here.
4. Please pay attention to the impact of input/output efficiency on your program.

Translated by ChatGPT 5