P9396 「DBOI」Round 1 未完成的约定

> _生活快得停不下来_\ _璀璨的也最终衰败_\ _他感到负荷已过载_\ _车窗外_\ _天上大朵云彩_\ _追随他的速度跑得飞快_\ _不由自主比赛_\ ——《笨小孩的道歉信》 不管多少个日夜，为你一直唱。

$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}$ 的结果。 **本题有多组数据。**

为避免输入量过大，你需要使用下面的方式读入，因此请将这段代码复制到你的代码中。**下列程序与此题做法无关，请仔细阅读示例代码中的注释。** ```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);} ull rand() { ull now = SC; now += !(now & 1); SA ^= SA > 13, SA ^= SA 13, SA ^= SA

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

| 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$ | **请注意常数因子对程序效率的影响。**