P9396 "DBOI" Round 1 Unfinished Promise.

> _Life moves so fast it will not stop_\ _What is dazzling will eventually fade_\ _He feels the load has already overloaded_\ _Outside the car window_\ _Big clouds in the sky_\ _Run fast, following his speed_\ _Involuntarily competing_\ — “An Apology Letter from a Silly Kid” No matter how many days and nights, I keep singing for you.

$m^3$ can be written as the sum of $m$ consecutive odd numbers $(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 $$ Under the influence of Zuo Ang’s fanatic worship of odd numbers, all the songs Su Xinhao writes will only have odd lengths. Obviously, a song’s length cannot be negative. For a song of length $x$, its pleasantness value $f(x)$ satisfies the following: after writing $f(x)^3$ according to the rule above, $x$ is one of the addends. For example, $f(21) = 5$, $f(11) = 3$, and $f(3) = 2$. On the next day, Zuo Ang came to visit and found that Su Xinhao had only written one song, and looked down on him. Su Xinhao got angry and wrote all songs whose lengths are odd within $1 \sim k$. Now Zuo Ang wants to know the sum of the pleasantness values of all Su Xinhao’s songs, to estimate the effect of his fanatic worship. That is: given a positive odd number $k(1\leqslant k< 2^{64})$, find $s = \sum\limits_{i = 1}^{\frac{k + 1}{2}} f(2\times i - 1)$, i.e. $f(1) + f(3) + f(5) + \cdots + f(k)$. Since Su Xinhao is really angry, the pleasantness values of the songs he wrote may be extremely large. You only need to output the result of $s\bmod{10^9 + 7}$. **This problem has multiple test cases.**

To avoid an excessively large input, you need to read input in the following way, so please copy this code into your program. **The following code is unrelated to the solution of this problem. Please read the comments in the sample code carefully.** ```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

Output $T$ lines, each containing one number $s\bmod{10^9 + 7}$, where $s$ is the sum of the pleasantness values of Su Xinhao’s songs.

| Subtask | Constraints | Score | |:----:|:----:|:----:| | 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$ | **Please pay attention to the impact of constant factors on the program’s efficiency.** Translated by ChatGPT 5