Background

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)]!

Problem Description

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.

Input Format

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.

Output Format

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

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

Hint

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