Background

The annual Gensokyo Mathematics Contest (thMO) is about to begin again.

The young (actually old) girls (actually housewives) who study math in Gensokyo, together with the ice fairy baka, are preparing for thMO.

But at that moment, the day-by-day peace of Gensokyo was broken.

On the radio, a song of death started playing!

At that moment, people recalled the fear of being ruled by arithmetic again.

Only the voice of baka, baka, baka, baka echoed throughout Gensokyo.

---

Kawashiro Nitori is sitting in the thMO2019 exam room!
Because Nitori has her supercomputer, after successfully covering it with optical camouflage, she became unstoppable in the thMO2019 exam.

• Nitori used her supercomputer to solve this problem in $0 \,\mathrm{ms}$:

  • $\exists \{ a_n\} (n=0,1,\cdots ,10^{18})$，given $a_0=2,a_1=5,a_{n+2}=3a_{n+1}-2a_n$, find $a_n\bmod 10^{9}+7$

• Nitori: Obviously, this can be done with matrix multiplication + fast exponentiation, and you can pass it in $O(\log n)$, roughly like this:

$$\begin{bmatrix} a_n & a_{n+1} \end{bmatrix}=\begin{bmatrix} a_0 & a_1 \end{bmatrix} \times \begin{bmatrix} 3 & 1 \\ -2 & 0 \end{bmatrix}^n$$

But Nitori encountered a problem she cannot solve, and she is asking for your help!

Problem Description

There exists a sequence $\{ a_n\} (n\in \{ 0,1,2,\cdots ,2^{64}-1\} )$.
Given $a_0=-3,a_1=-6,a_2=-12,a_n=3a_{n-1}+a_{n-2}-3a_{n-3}+3^n$.

• Now you are given a non-negative integer $n$. Let $p=10^{9}+7$. Please compute $a_n \bmod p$.

• Note: if $a_n<0$, please output $(a_n \bmod p+p)\bmod p$.

To test your skills more thoroughly, Nitori prepared $T$ queries.

• To reduce the amount of input and output to some extent, we generate the queries using the following code:

namespace Mker
{
//  Powered By Kawashiro_Nitori
//  Made In Gensokyo, Nihon
	#include<climits>
	#define ull unsigned long long
	#define uint unsigned int
	ull sd;int op;
	inline void init() {scanf("%llu %d", &sd, &op);}
	inline ull ull_rand()
	{
		sd ^= sd << 43;
		sd ^= sd >> 29;
		sd ^= sd << 34;
		return sd;
	}
	inline ull rand()
	{
		if (op == 0) return ull_rand() % USHRT_MAX + 1;
		if (op == 1) return ull_rand() % UINT_MAX + 1; 
		if (op == 2) return ull_rand();
	}
}

After calling Mker::init(), the value returned by your $i$-th call to Mker::rand() is the $n_i$ of the $i$-th query.

The constraints on $op$ are as follows:

• If $op=0$, then $n_i \leq 2^{16}$.

• If $op=1$, then $n_i \leq 2^{32}$.

• If $op=2$, then $n_i \leq 2^{64}-1$.

To reduce your output size, you only need to output the xor sum of the answers of all queries.

Input Format

The first line contains three integers: $T$, $seed$, and $op$.

Output Format

Output one integer: the xor sum of the answers to the $T$ queries.

142857 1145141919 0

562611141

142857 1145141919 1

894946216

142857 1145141919 2

771134436

Hint

Subtasks

Source

Lost Home 2019 League (MtOI2019) T4

Problem setter: disangan233

Problem tester: suwakow

Translated by ChatGPT 5