题目背景

Rolling_Code 是一个喜欢音游的女孩子。

Rolling_Code 打 $\aleph_0$ 的成绩如下：

然而这并不是 IN。

慢报：Rolling_Code 将 Aleph-0 [IN 15(15.7)] All Perfect 了！

题目描述

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 不会做，因此找你求助。

输入格式

本题有多组数据。

第一行一个数字 $t$，代表数据组数。

接下来 $t$ 行每行两个数字 $r_i,k_i$，表示第 $i$ 次询问中的 $r,k$。

输出格式

每行一个数字 $S_i$，表示第 $i$ 次询问的答案。

5
1 2
14 2
51 2
4 2
1919810 2

1
6480
495741
57
936062395

5
43752 25
26701 25
43734 25
37553 25
67839 25

252345090
86394269
406573405
129371352
118835650

提示

本题采用捆绑测试。

本题有多组数据。

对于 $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$。