P8440 Aleph-0 (Fan-made LGC 7)

Rolling_Code is a girl who likes rhythm games.  Rolling_Code’s score when playing $\aleph_0$ is as follows:  ~~However, this is not an IN.~~ Breaking news: Rolling_Code achieved All Perfect on Aleph-0 [IN 15(15.7)]!

As a math teacher, LeaF has opened a series of perfect math classes. The students include: Rolling_Code, you, and Miuho. Teaching assistant: Cirno. In the first class, there is an exam. Students who solve this problem can get early access to a special edition of $\aleph_0$! — LeaF ~~Aleph-0 (Legacy - SP Lv.?)~~ Rolling_Code is very interested in rhythm games, so she also really wants to get this song. But when she opened the problem statement, she was shocked: > $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}$ Compute $S=\left(\sum\limits_{i=0}^{r} f^k(i)\right)\bmod (10^9+7)$. Here, $f^k(i)=(f(i))^k$. Originally, the answer for $r\rightarrow\aleph_0$ was desired, but unfortunately it is not defined, so the range of $r$ is made smaller. — LeaF For some reason, LeaF defines $0^0=1$. To make it more interesting, LeaF also added multiple queries for $r,k$. Rolling_Code cannot solve it, so she asks you for help.

**This problem has multiple test cases.** The first line contains an integer $t$, the number of test cases. The next $t$ lines each contain two integers $r_i,k_i$, meaning the $r,k$ in the $i$-th query.

For each test case, output one integer $S_i$, the answer to the $i$-th query.

**This problem uses bundled testdata.** **This problem has multiple test cases.** For $100\%$ of the testdata, it is guaranteed that $1\le t\le 10^3,1\le r\le 2^{63}-1,0\le k\le 30$. Subtask 1: For $5\%$ of the testdata, it is guaranteed that $1\le t\le 100,1\le r\le 10^4$. Subtask 2: For $10\%$ of the testdata, it is guaranteed that $1\le t\le 1000,1\le r\le 10^5$, **depends on Subtask 1**. Subtask 3: For $10\%$ of the testdata, it is guaranteed that $1\le t\le 1000,1\le r\le 10^6$, and $k$ is a fixed value. Subtask 4: For $25\%$ of the testdata, it is guaranteed that $k=2$. Subtask 5: For the last $50\%$ of the testdata, there are no special constraints, **depends on Subtask 1, 2, 3, 4**. --- ### Sample Explanation $f_0=0,f_1=1,f_2=2,f_3=6,f_4=4$. For $r=4,k=2$, $\text{Ans}=0^2+1^2+2^2+6^2+4^2=57$. Translated by ChatGPT 5