题目描述

一年一度的幻想乡数学竞赛 (thMO) 又要开始了。

幻想乡中学习数学的少 (lao) 女 (tai) 们 (po) 和冰之妖精 baka 一起准备着 thMO。

但是在那一刻，幻想乡日复一日的宁静被打破了。

广播里，播放起了死亡的歌曲！

在那一刻，人们又回想起了被算数支配的恐惧。

就剩下 baka，baka，baka，baka 的声音在幻想乡里回荡。

河城 荷取 (Kawashiro Nitori) 正坐在 thMO2019 的考场上！

因为荷取有着她的超级计算机，在成功地用光学迷彩覆盖了计算机之后，荷取在 thMO2019 的考场上所向披靡。

• 荷取用她的超级计算机 $0 \,\mathrm{ms}$ 跑出了这么一道题：

  • $\exists { a_n} (n=0,1,\cdots ,10^{18})$，已知 $a_0=2,a1=5,a{n+2}=3a_{n+1}-2a_n$，求 $a_n\bmod 10^{9}+7$
• 荷取：显然，这个题可以用矩阵乘法 + 快速幂，可以 $O(\log n)$ 水过去，差不多就这样：

$$ \begin{bmatrix} an & a{n+1} \end{bmatrix}=\begin{bmatrix} a_1 & a_2 \end{bmatrix} \times \begin{bmatrix} 3 & 1 \ -2 & 0 \end{bmatrix}^n $$

但是荷取遇到了一道她不会的题，她正在寻求你的帮助呢！

存在一个数列 ${ a_n} (n\in { 0,1,2,\cdots ,2^{64}-1} )$。

已知 $a_0=-3,a_1=-6,a_2=-12,an=3a{n-1}+a{n-2}-3a{n-3}+3^n$。

• 现在给你一个非负整数 $n$ ，令 $p=10^{9}+7$，请你求出 $a_n \bmod p$。

• 注：若 $a_n<0$ ，请输出 $(a_n \bmod p+p)\bmod p$。

为了更充分地考验你的水平，荷取设置了 $T$ 组询问。

• 为了在某种程度上减少你的输入和输出量，我们采用以下的代码来生成询问：

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

在调用 Mker::init() 函数之后，你第 $i$ 次调用 Mker::rand() 函数时返回的便是第 $i$ 次询问的 $n_i$。

在这里给出 $op$ 的限制：

• 如果 $op=0$，满足 $n_i \leq 2^{16}$。

• 如果 $op=1$，满足 $n_i \leq 2^{32}$。

• 如果 $op=2$，满足 $n_i \leq 2^{64}-1$。

为了减少你的输出量，你只需要输出所有询问答案的异或和。

输入格式

第一行三个整数，输入 $T$，$seed$ 和 $op$。

输出格式

第一行一个整数，输出 $T$ 组询问的答案的异或和。

样例 1

input

142857 1145141919 0

output

562611141

样例 2

input

142857 1145141919 1

output

894946216

样例 3

input

142857 1145141919 2

output

771134436

数据范围与提示

子任务

题目来源

迷途之家 2019 联赛 (MtOI2019) T4

出题人：disangan233

验题人：suwakow