题目描述

有 $T$ 组询问，每次给定两个正整数 $n,l$，

你需要构造一个长度为 $l$ 的正整数序列 $a$（编号从 $1$ 至 $l$），

且满足 $\forall i\in[1,l]$，都有 $a_i\in[1,n]$。

求：

的最大值。

为了避免答案过大，对于每组询问，只需要输出这个最大值对 $10^9+7$ 取模的结果。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来第 $2$ 行到第 $T+1$ 行，每行两个整数 $n,l$ ，分别代表 $a_i$ 的最大取值与 $a$ 的长度。

输出格式

共 $T$ 行，每行一个整数，对应每组询问的答案对 $10^9+7$ 取模的结果。

1
2 3

6

2
114 514
1919 180

8388223
16580700

提示

【样例解释 #1】
当 $n=2,l=3$，$a$ 取 $\{1,2,1\}$ 的任一排列时可以得到最大值，为 $(1\oplus2)+(1\oplus1)+(2\oplus1)=6$，易证明此时原式有最大值。

【数据规模与约定】 | 测试点编号 | $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$ |

对于 $100\%$ 的数据，满足 $1\le T\le 5\times10^5$，$1\le n\le 10^{12}$，$2\le l \le 10^5$。

【提示】

1. 「$\oplus$」是按位异或符号。如果您不知道什么是按位异或，可以参考这里。
2. 取模是一种运算，$a$ 对 $b$ 取模代表将 $a$ 赋值为 $a$ 除以 $b$ 所得到的余数。
   在 C++ / Python 中的取模符号为 %，在 Pascal 中的取模符号为 mod。
3. $\sum$ 是求和符号。如果您不知道什么是 $\sum$ 符号，可以参考这里。
4. 请注意数据的读入输出对程序效率造成的影响。