Background

shadowice1984 found a problem: compute the $n$-th term of the Fibonacci sequence modulo $10^9+7$, where $n \leq 10^9$.

shadowice1984 thought about it for a whole week but still could not solve it.

Of course, that was when shadowice1984 had just started learning OI. Today, he learned fast matrix exponentiation and spent an entire day solving the problem above.

He decided to make a problem to test your fast matrix exponentiation skills. To check whether the std he spent a week writing has any mistakes, he decided to ask you to help verify the problem.

Problem Description

Given a sequence $a$ that satisfies the recurrence

Compute the value of the $n$-th term of this sequence modulo $10^9+7$. There are $T$ queries in total.

To reduce your input and output workload to some extent, we generate the queries using the following code:

namespace Mker
{
	unsigned long long SA,SB,SC;
	void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
	unsigned long long rand()
	{
	    SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
	    unsigned long long t=SA;
		SA=SB,SB=SC,SC^=t^SA;return SC;
	}
}

After calling Mker::init(), this random number generator will work normally. When you call Mker::rand() for the $i$-th time, the returned value is the $n$ for the $i$-th query.

To reduce your output, you only need to output the bitwise XOR of the answers to all queries.

Input Format

A single line with four integers, representing $T,SA,SB,SC$. After reading $T$, you can directly call Mker::init() to finish the input.

Output Format

A single line with one integer, representing the bitwise XOR of all answers.

4779 17790102303135 73152356900611 22086182463002

391030355

49999561 116754637679537 79587668206509 80161279644028

705437004

Hint

$SA,SB,SC$ are all within the range of the unsigned long long data type, so the returned $n$ is also within the range of the unsigned long long data type.

The first 6 test points are worth $1$ point each.

For test points 1 and 2, $T \leq 5000$.

For test points 3, 4, 5, and 6, $T \leq 500000$.

For all test points, $1 \leq T \leq 5×10^7$。

Translated by ChatGPT 5