LeaF 作为数学教师开办了一系列完美数学课堂，参加的学生包括了：Rolling_Code，你，美穗。助教：琪露诺。
第一节课，考试。
做出这道题目的同学可以获得特殊版 $\aleph_0$ 的率先游玩机会哦！——LeaF
~~Aleph-0 (Legacy - SP Lv.?)~~
Rolling_Code 对音游非常感兴趣，所以也非常想要获得这首曲子。但是它打开题面的时候震惊了：
> $f(x)=\begin{cases}0&x=0\\1&x=1\\2f(\frac{x}{2})&2|x\operatorname{and} x>0 \\ 2f(\frac{x-1}{2})+\frac{2}{x-1}f(\frac{x-1}{2})+x&\text{otherwise}\end{cases}$
求 $S=\left(\sum\limits_{i=0}^{r} f^k(i)\right)\bmod (10^9+7)$。
其中 $f^k(i)=(f(i))^k$。
本来是想要求 $r\rightarrow\aleph_0$ 的答案，可惜了啊，没有被定义，那就把 $r$ 范围放小一点吧。——LeaF
由于某些原因，LeaF 定义 $0^0=1$。
为了增加趣味，LeaF 还增加了多次对于 $r,k$ 的询问。
Rolling_Code 不会做，因此找你求助。
## Input
**本题有多组数据。**
第一行一个数字 $t$，代表数据组数。
接下来 $t$ 行每行两个数字 $r_i,k_i$，表示第 $i$ 次询问中的 $r,k$。
## Output
每行一个数字 $S_i$，表示第 $i$ 次询问的答案。
[samples]
## Background
Rolling_Code 是一个喜欢音游的女孩子。
Rolling_Code 打 $\aleph_0$ 的成绩如下：
~~然而这并不是 IN。~~
慢报：Rolling_Code 将 Aleph-0 [IN 15(15.7)] All Perfect 了！
## Note
**本题采用捆绑测试。**
**本题有多组数据。**
对于 $100\%$ 的数据，保证 $1\le t\le 10^3,1\le r\le 2^{63}-1,0\le k\le 30$。
Subtask 1：对于 $5\%$ 的数据，保证 $1\le t\le 100,1\le r\le 10^4$。
Subtask 2：对于 $10\%$ 的数据，保证 $1\le t\le 1000,1\le r\le 10^5$，**依赖于 Subtask 1**。
Subtask 3：对于 $10\%$ 的数据，保证 $1\le t\le 1000,1\le r\le 10^6,k$ 为定值。
Subtask 4：对于 $25\%$ 的数据：保证 $k=2$。
Subtask 5：对于最后 $50\%$ 的数据，无特殊限制，**依赖于 Subtask 1，2，3，4**。
---
### 样例解释
$f_0=0,f_1=1,f_2=2,f_3=6,f_4=4$。
对于 $r=4,k=2$ 的情况，$\text{Ans}=0^2+1^2+2^2+6^2+4^2=57$。