P6599 "EZEC-2" XOR

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: $$\sum_{i=1}^l\sum_{j=1}^{i-1}a_i\oplus a_j$$ To avoid the answer being too large, for each query, you only need to output this maximum value modulo $10^9+7$.

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 $T$ lines, each containing one integer: the answer for the corresponding query modulo $10^9+7$.

**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](https://oi-wiki.org/math/bit/#_1). 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](https://baike.baidu.com/item/∑/1233796?fr=aladdin). 4. Please pay attention to the impact of input/output efficiency on your program. Translated by ChatGPT 5