Background

The annual Mathematical Competition in FANTASY (thMO) is about to begin.

The young (old) girls (ladies) who study mathematics in FANTASY and the ice fairy baka are preparing for thMO.

But at that moment, the peaceful days of FANTASY were shattered.

The broadcast played a deadly song!

At that moment, people remembered the fear of being dominated by arithmetic.

Only the sounds of baka, baka, baka, baka echoed in FANTASY.

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

• Nitori used her supercomputer to quickly solve a 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 problem can be solved with matrix multiplication + fast exponentiation, which can be done 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 couldn't solve and is seeking 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, given a non-negative integer $n$, let $p=10^9+7$, please find $a_n \bmod p$.

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

To fully test your skills, Nitori set up $T$ queries.

• To reduce your input and output volume, we use the following code to generate queries:

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() function, the $i$-th call to Mker::rand() function returns the $i$-th query's $n_i$.

Here are the restrictions for $op$:

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

To reduce your output volume, you only need to output the XOR sum of all query answers.

Input Format

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

Output Format

The first line contains one integer, the XOR sum of the answers for $T$ queries.

Sample Input and Output

Input Sample #1

142857 1145141919 0

Output Sample #1

562611141

Input Sample #2

142857 1145141919 1

Output Sample #2

894946216

Input Sample #3

142857 1145141919 2

Output Sample #3

771134436

Notes/Hints

Subtasks

Problem Source

Lost Home 2019 League (MtOI2019) T4

Problem Author: disangan233

Problem Tester: suwakow

见题面 Input 部分

见题面 Output 部分