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