题目背景

生活快得停不下来
璀璨的也最终衰败
他感到负荷已过载
车窗外
天上大朵云彩
追随他的速度跑得飞快
不由自主比赛
——《笨小孩的道歉信》

不管多少个日夜，为你一直唱。

题目描述

$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}$ 的结果。

本题有多组数据。

输入格式

为避免输入量过大，你需要使用下面的方式读入，因此请将这段代码复制到你的代码中。下列程序与此题做法无关，请仔细阅读示例代码中的注释。

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()。

示例代码：

#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;
}

输出格式

$T$ 行，每行一个数 $s\bmod{10^9 + 7}$，其中 $s$ 表示苏信好的歌的悦耳值之和。

1 114514 1919810 19950501 5

35

5 231421 523434 31243 5

50
30
40
55
35

提示

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$

请注意常数因子对程序效率的影响。