Perfect Math Classroom: The Aleph-0 Challenge

LeaF, a mathematics teacher, has started a series of Perfect Math Classes. Among the students are Rolling_Code, you, and 美穗, with assistant teacher 琪露诺. In the first class, there is an exam. Solve the following problem to get an exclusive early play chance of the special edition \(\aleph_0\) game!

The function \(f(x)\) is defined as follows:

[ f(x)=\begin{cases} 0, & x=0,\ 1, & x=1,\ 2f\left(\frac{x}{2}\right), & \text{if }2\mid x \text{ and } x>0,\ 2f\left(\frac{x-1}{2}\right)+\frac{2}{x-1}f\left(\frac{x-1}{2}\right)+x, & \text{otherwise.} \end{cases} ]

Note: For this problem, \(f^k(i)\) is defined as \((f(i))^k\). Also, due to certain reasons, we define \(0^0=1\). Originally, the sum was intended for \(r\rightarrow\aleph_0\) but since that is not well-defined, the range for \(r\) has been reduced.

Your task is to answer multiple queries. Each query gives two integers \(r\) and \(k\). For each query, compute

[ S=\left(\sum_{i=0}^{r} f^k(i)\right) \bmod (10^9+7). ]

Help Rolling_Code get the song by solving this challenge!

inputFormat

The first line contains an integer \(T\) representing the number of queries.

Each of the following \(T\) lines contains two integers \(r\) and \(k\), separated by a space.

Constraints: \(r\) is small enough for direct computation.

outputFormat

For each query, output a single line containing the value of \(S\) computed modulo \(10^9+7\).

sample

4
1 1
3 2
5 0
7 1

1
41
6
56