[MtOI2019] 幻想乡数学竞赛

题目背景

一年一度的幻想乡数学竞赛 (thMO) 又要开始了。 幻想乡中学习数学的少 (lao) 女 (tai) 们 (po) 和冰之妖精 baka 一起准备着 thMO。 但是在那一刻,幻想乡日复一日的宁静被打破了。 广播里,播放起了死亡的歌曲! 在那一刻,人们又回想起了被算数支配的恐惧。 就剩下 baka,baka,baka,baka 的声音在幻想乡里回荡。 --- 河城 荷取 (Kawashiro Nitori) 正坐在 thMO2019 的考场上! 因为荷取有着她的[超级计算机](https://www.luogu.org/problemnew/show/P4911),在成功地用光学迷彩覆盖了计算机之后,荷取在 thMO2019 的考场上所向披靡。 * 荷取用她的超级计算机 $0 \,\mathrm{ms}$ 跑出了这么一道题: * $\exists \{ a_n\} (n=0,1,\cdots ,10^{18})$,已知 $a_0=2,a_1=5,a_{n+2}=3a_{n+1}-2a_n$,求 $a_n\bmod 10^{9}+7$ * 荷取:显然,这个题可以用矩阵乘法 + 快速幂,可以 $O(\log n)$ 水过去,差不多就这样: $$ \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 $$ 但是荷取遇到了一道她不会的题,她正在寻求你的帮助呢!

题目描述

存在一个数列 $\{ a_n\} (n\in \{ 0,1,2,\cdots ,2^{64}-1\} )$。 已知 $a_0=-3,a_1=-6,a_2=-12,a_n=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$ 组询问。 * 为了在某种程度上减少你的输入和输出量,我们采用以下的代码来生成询问: ```cpp 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

142857 1145141919 0

输出样例 #1

562611141

输入样例 #2

142857 1145141919 1

输出样例 #2

894946216

输入样例 #3

142857 1145141919 2

输出样例 #3

771134436

说明

### 子任务 ![png](https://i.loli.net/2019/04/19/5cb9bb2c6c1d6.png) ### 题目来源 [迷途之家 2019 联赛](https://www.luogu.org/contest/20135)(MtOI2019) T4 出题人:disangan233 验题人:suwakow