$m^3$ 可以表示为 $m$ 个连续奇数的和 $(m \geqslant 1)$：
$$
1^3 = 1\\
2^3 = 3 + 5\\
3^3 = 7 + 9 + 11\\
4^3 = 13 + 15 + 17 + 19\\
5^3 = 21 + 23 + 25 + 27 + 29\\
\cdots\cdots
$$
在左昂对奇数的狂热崇拜的影响下，苏信好写出来的歌只会是奇数长度。显然歌曲的长度不能是负数。
对于一首长度为 $x$ 的歌，它的悦耳值 $f(x)$ 满足将 $f(x)^3$ 按照上面的规律表示出来后，$x$ 是其中的一个加数。例如 $f(21) = 5, f(11) = 3,f(3) = 2$。
第二天，左昂前来参观，发现苏信好只写出来了一首歌，鄙夷不已。苏信好怒从心起，写出了以 $1\sim k$ 内所有长度为奇数的歌。
现在左昂想要知道苏信好所有歌的悦耳值之和，以预估他的狂热崇拜的效果。即：给定一个正奇数 $k(1\leqslant k< 2^{64})$，求 $s = \sum\limits_{i = 1}^{\frac{k + 1}{2}} f(2\times i - 1)$，即 $f(1) + f(3) + f(5) + \cdots +f(k)$。
由于苏信好实在太生气，写出来的歌的悦耳值可能十分之大，你只需要输出 $s\bmod{10^9 + 7}$ 的结果。
**本题有多组数据。**
## Input
为避免输入量过大，你需要使用下面的方式读入，因此请将这段代码复制到你的代码中。**下列程序与此题做法无关，请仔细阅读示例代码中的注释。**
```cpp
namespace Mker {
typedef unsigned long long ull;
ull SA, SB, SC, p = -1;
int base;
void init(){scanf("%llu%llu%llu%d", &SA, &SB, &SC, &base); p = p << (65 - base) >> (65 - base);}
ull rand() {
ull now = SC; now += !(now & 1);
SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
ull t = SA;
return SA = SB, SB = SC, SC ^= t ^ SA, (now & p) + p + 1;
}
}
```
先读入一个数 $T$，表示数据组数，然后你**需要调用** `Mker::init()`。这个函数将输入四个数 $SA,SB,SC,base$，表示对于这组数据，$k<2^{base}$。
接下来，对于每一组询问，你应当令 $k$ 的值即为 `Mker::rand()`。
示例代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int T;
namespace Mker {
typedef unsigned long long ull;
ull SA, SB, SC, p = -1;
int base;
void init(){scanf("%llu%llu%llu%d", &SA, &SB, &SC, &base); p = p << (65 - base) >> (65 - base);}
ull rand() {
ull now = SC; now += !(now & 1);
SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
ull t = SA;
return SA = SB, SB = SC, SC ^= t ^ SA, (now & p) + p + 1;
}
}
int main() {
scanf("%d", &T); Mker::init(); // 不要忘记 init
// cout << Mker::base << endl; 你可以通过这种方式输出得到 base 的值
while (T--) {
unsigned long long k = Mker::rand(); // 通过这种方式，获得一次询问的 k
if (k == 1) puts("1");
else if (k == 17) puts("26");
else puts("I AK IOI");
// cout << k << endl; 你可以通过这种方式输出得到真实的 k 以调试代码
}
return 0;
}
```
## Output
$T$ 行，每行一个数 $s\bmod{10^9 + 7}$，其中 $s$ 表示苏信好的歌的悦耳值之和。
[samples]
## Background
> _生活快得停不下来_\
_璀璨的也最终衰败_\
_他感到负荷已过载_\
_车窗外_\
_天上大朵云彩_\
_追随他的速度跑得飞快_\
_不由自主比赛_\
——《笨小孩的道歉信》
不管多少个日夜，为你一直唱。
## Note
| Subtask | 数据范围 | 分值 |
|:----:|:----:|:----:|
| Subtask 1 | $T=1$，$k< 2^{25}$ | $20$ |
| Subtask 2 | $T\leq 5$，$k< 2^{48}$ | $30$ |
| Subtask 3 | $T\leq 10^6$，$k < 2^{48}$ | $40$ |
| Subtask 4 | $T\leq 3\times 10^6$，$k < 2^{64}$ | $10$ |
**请注意常数因子对程序效率的影响。**