Background

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.

Problem Description

$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.

Input Format

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.

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

First read an integer $T$, the number of test cases, then you must call Mker::init(). This function reads four numbers $SA, SB, SC, base$, indicating that for this set of testdata, $k<2^{base}$.

Next, for each query, you should set the value of $k$ to Mker::rand().

Sample code:

#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(); // Do not forget init.
//	cout << Mker::base << endl; You can output base in this way.
	while (T--) {
		unsigned long long k = Mker::rand(); // Get k for one query in this way.
		if (k == 1) puts("1");
		else if (k == 17) puts("26");
		else puts("I AK IOI");
		
//		cout << k << endl; You can output the real k in this way to debug your code.
	}
	return 0;
}

Output Format

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.

1 114514 1919810 19950501 5

35

5 231421 523434 31243 5

50
30
40
55
35

Hint

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