{"raw_statement":[{"iden":"background","content":"Rolling_Code 是一个喜欢音游的女孩子。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/rnkqui18.png)\n\nRolling_Code 打 $\\aleph_0$ 的成绩如下：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/q298dfbe.png)\n\n~~然而这并不是 IN。~~\n\n慢报：Rolling_Code 将 Aleph-0 [IN 15(15.7)] All Perfect 了！"},{"iden":"statement","content":"LeaF 作为数学教师开办了一系列完美数学课堂，参加的学生包括了：Rolling_Code，你，美穗。助教：琪露诺。\n\n第一节课，考试。\n\n做出这道题目的同学可以获得特殊版 $\\aleph_0$ 的率先游玩机会哦！——LeaF\n\n~~Aleph-0 (Legacy - SP Lv.?)~~\n\nRolling_Code 对音游非常感兴趣，所以也非常想要获得这首曲子。但是它打开题面的时候震惊了：\n\n> $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}$\n\n求 $S=\\left(\\sum\\limits_{i=0}^{r} f^k(i)\\right)\\bmod (10^9+7)$。\n\n其中 $f^k(i)=(f(i))^k$。\n\n本来是想要求 $r\\rightarrow\\aleph_0$ 的答案，可惜了啊，没有被定义，那就把 $r$ 范围放小一点吧。——LeaF\n\n由于某些原因，LeaF 定义 $0^0=1$。\n\n为了增加趣味，LeaF 还增加了多次对于 $r,k$ 的询问。\n\nRolling_Code 不会做，因此找你求助。\n"},{"iden":"input","content":"**本题有多组数据。**\n\n第一行一个数字 $t$，代表数据组数。\n\n接下来 $t$ 行每行两个数字 $r_i,k_i$，表示第 $i$ 次询问中的 $r,k$。\n"},{"iden":"output","content":"每行一个数字 $S_i$，表示第 $i$ 次询问的答案。\n"},{"iden":"note","content":"\n**本题采用捆绑测试。**\n\n**本题有多组数据。**\n\n对于 $100\\%$ 的数据，保证 $1\\le t\\le 10^3,1\\le r\\le 2^{63}-1,0\\le k\\le 30$。\n\nSubtask 1：对于 $5\\%$ 的数据，保证 $1\\le t\\le 100,1\\le r\\le 10^4$。\n\nSubtask 2：对于 $10\\%$ 的数据，保证 $1\\le t\\le 1000,1\\le r\\le 10^5$，**依赖于 Subtask 1**。\n\nSubtask 3：对于 $10\\%$ 的数据，保证 $1\\le t\\le 1000,1\\le r\\le 10^6,k$ 为定值。\n\nSubtask 4：对于 $25\\%$ 的数据：保证 $k=2$。\n\nSubtask 5：对于最后 $50\\%$ 的数据，无特殊限制，**依赖于 Subtask 1，2，3，4**。\n\n---\n\n### 样例解释\n\n$f_0=0,f_1=1,f_2=2,f_3=6,f_4=4$。\n\n对于 $r=4,k=2$ 的情况，$\\text{Ans}=0^2+1^2+2^2+6^2+4^2=57$。"}],"translated_statement":null,"sample_group":[["5\n1 2\n14 2\n51 2\n4 2\n1919810 2","1\n6480\n495741\n57\n936062395"],["5\n43752 25\n26701 25\n43734 25\n37553 25\n67839 25","252345090\n86394269\n406573405\n129371352\n118835650"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}