题目背景

shadowice1984 发现了一道题：求斐波那契数列第 $n$ 项模 $10^9+7$ 的值，$n \leq 10^9$。

shadowice1984 想了一个星期可他还是不会做。

当然，这是 shadowice1984 刚学 OI 时候的事情了，今天他学习了矩阵快速幂并且花了一整天解决了上面的问题。

他决定出一道题来测试你的矩阵快速幂水平如何，为了检查他花了一个星期写出的 std 到底有没有错，他决定让你来帮他验题。

题目描述

给定一个数列 $a$ 满足递推式

求这个数列第 $n$ 项模 $10^9+7$ 的值，一共有 $T$ 组询问。

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

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

在调用 Mker::init() 函数之后这个随机数生成器便可以正常工作了，当你第 $i$ 次调用 Mker::rand() 函数时返回的便是第 $i$ 次询问的 $n$ 值。

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

输入格式

仅一行四个整数，表示 $T,SA,SB,SC$ 的值，你可以在读入 $T$ 之后直接调用 Mker::init() 来完成输入工作。

输出格式

仅一行一个整数，表示所有答案的异或和。

4779 17790102303135 73152356900611 22086182463002

391030355

49999561 116754637679537 79587668206509 80161279644028

705437004

提示

$SA,SB,SC$ 均在 unsigned long long 数据类型的范围之内，由此可以发现返回的 $n$ 值也是 unsigned long long 数据类型的范围之内。

前 6 个测试点每个测试点 $1$ 分。

对于 1,2 测试点 $T \leq 5000$。

对于 3,4,5,6 测试点 $T \leq 500000$。

对于所有测试点 $1 \leq T \leq 5\times 10^7$。