为啥我就没看出来有循环节呢……
打表可得，这个数列是有循环节的，循环节为(10^9+6)，然后分块预处理，即取(k=sqrt(10^9+6))，然后分别预处理出转移矩阵(A)的(A^1,A^2,...,A^{k-1})和(A^k,A^{2k},...)，那么每一次就能(O(1))回答询问了
注意常数问题……这份代码勉强卡过……建议矩阵里的元素别开数组直接用四个变量存会快一点……
//minamoto
#include<bits/stdc++.h>
#define R register
#define ull unsigned long long
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
const int N=4e4+5,P=1e9+7;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
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;
}
}
struct Matrix{
int a[2][2];
Matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;}
int* operator [](const int &x){return a[x];}
Matrix operator *(Matrix b){
Matrix res;
res[0][0]=add(1ll*a[0][0]*b[0][0]%P,1ll*a[0][1]*b[1][0]%P);
res[0][1]=add(1ll*a[0][0]*b[0][1]%P,1ll*a[0][1]*b[1][1]%P);
res[1][0]=add(1ll*a[1][0]*b[0][0]%P,1ll*a[1][1]*b[1][0]%P);
res[1][1]=add(1ll*a[1][0]*b[0][1]%P,1ll*a[1][1]*b[1][1]%P);
return res;
}
}bin1[N],bin2[N],res;int ans,T,n,len;
void init(){
res[0][0]=233,res[0][1]=1,res[1][0]=666,bin1[1]=res;
len=sqrt(1e9+6),bin1[0][0][0]=bin1[0][1][1]=bin2[0][0][0]=bin2[0][1][1]=1;
fp(i,2,len-1)bin1[i]=bin1[i-1]*res;bin2[1]=bin1[len-1]*res;
fp(i,2,len+1)bin2[i]=bin2[i-1]*bin2[1];
}
int main(){
// freopen("testdata.in","r",stdin);
init(),scanf("%d",&T);Mker::init();
while(T--){
Matrix res;n=Mker::rand()%(P-1);
res[0][0]=1;
if(n<=1)ans^=n;
else res=res*bin2[(n-1)/len]*bin1[(n-1)%len],ans^=res[0][0];
}printf("%d
",ans);return 0;
}