Maximum XOR Sum Sequence

You are given T queries. In each query, you are provided two positive integers n and l.

Your task is to construct a sequence \(a = [a_1, a_2, \dots, a_l]\) of positive integers such that \(1 \le a_i \le n\) for all \(1 \le i \le l\), in order to maximize the following sum:

\[ S = \sum_{i=1}^{l} \sum_{j=1}^{i-1} \left(a_i \oplus a_j\right), \]

where \(\oplus\) denotes the bitwise XOR operation. Since the answer can be very large, output the maximum value modulo \(10^9+7\).

Hint: It can be shown that when \(n \ge 2\), there exist two numbers \(x\) and \(y\) in the range \([1,n]\) such that \(x \oplus y = 2^{k}-1\), where \(k = \lfloor \log_2 n \rfloor + 1\). An optimal strategy is to alternate between these two numbers as evenly as possible. If \(l_0\) and \(l_1\) denote the counts of these two numbers respectively (with \(l_0 + l_1 = l\) and as balanced as possible), then the maximum sum is \(l_0 \times l_1 \times (2^k-1)\). Note that when \(n = 1\) the only possibility is the sequence of all ones, resulting in a sum of 0.

inputFormat

The first line contains a single integer T (\(1 \le T \le 10^5\)), the number of queries.
Each of the next T lines contains two space‐separated positive integers n and l (\(1 \le n, l \le 10^9\)).

outputFormat

For each query, output a single line containing the maximum possible value of \(S\) modulo \(10^9+7\).

sample

1
2 3

6

</p>