题目描述

有T组询问，每次给定两个正整数$n,l$，你需要构造一个长度为$l$的正整数序列$a$（编号从$1$至$l$），且满足$\forall i\in[1,l]$，都有$a_i\in[1,n]$。求如下式子的最大值： $$\sum_{i=1}^{l}\sum_{j=1}^{i-1} (a_i \oplus a_j)$$ 为了避免答案过大，对于每组询问，只需要输出这个最大值对$10^9+7$取模的结果。

输入描述

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

输出描述

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

输入样例1

1
2 3

输出样例1

6

样例1解释

当$n=2,l=3$时，构造序列如$[1,2,1]$，所有$i>j$的异或和为$(2\oplus1)+(1\oplus1)+(1\oplus2) = 3+0+3=6$，为最大值。