记录编号	61196	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2012]随机数生成器	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2013-06-05 18:41:08	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int SIZEN=3;
ull A,C,X0,N,G,MOD;
/*ull quickmul(ull a,ull n){//a*n
	if(n==0) return 0;
	if(n==1) return a%MOD;
	ull ans=0,temp=a;
	while(n){
		if(n&1){
			ans+=temp;
			ans%=MOD;
		}
		temp+=temp;
		temp%+MOD;
		n>>=1;
	}
	return ans;
}*/
ull quickmul(ull a,ull b){
	ull ret;
	if(b==0) return 0;
	if(b==1) return a%MOD;
	ret=quickmul(a,b/2);
	ret+=ret;
	ret%=MOD;
	if(b%2)	ret+=a;
	return ret%MOD;
}
class MATRIX{
public:
	int n,m;//n行m列
	ull s[SIZEN][SIZEN];//真・矩阵
	//下标从1开始
	MATRIX(){n=m=0;}
	void output(void){
		cout<<n<<" "<<m<<endl;
		int i,j;
		for(i=1;i<=n;i++){for(j=1;j<=m;j++){cout<<s[i][j]<<" ";}cout<<endl;}cout<<endl;
	}
};
MATRIX operator * (MATRIX a,MATRIX b){
	MATRIX ans;
	//结果是一个a.n行,b.m列的矩阵,取模MOD
	ull i,j,k;
	if(a.m!=b.n) return ans;
	ans.n=a.n,ans.m=b.m;
	ull temp;
	for(i=1;i<=a.n;i++){
		for(j=1;j<=b.m;j++){
			ans.s[i][j]=0;
			for(k=1;k<=a.m;k++){
				temp=quickmul(a.s[i][k],b.s[k][j]);
				ans.s[i][j]+=temp;
				ans.s[i][j]%=MOD;
			}
		}
	}
	return ans;
}
MATRIX one;//单位矩阵
MATRIX mat_quickpow(MATRIX a,ull n){//矩阵的a^n
	MATRIX ans=one,temp=a;
	while(n){		
		if(n&1) ans=ans*temp;
		temp=temp*temp;
		n>>=1;
	}
	return ans;
}
void work(void){
	MATRIX rec,ans;
	rec.n=rec.m=2;
	rec.s[1][1]=A,rec.s[1][2]=0,rec.s[2][1]=C,rec.s[2][2]=1;
	rec=mat_quickpow(rec,N);
	ans.n=1,ans.m=2;
	ans.s[1][1]=X0,ans.s[1][2]=1;
	ans=ans*rec;
	cout<<ans.s[1][1]%G<<endl;
}
void init(void){
	cin>>MOD>>A>>C>>X0>>N>>G;
	A%=MOD,C%=MOD,X0%=MOD;
	one.n=one.m=2;
	one.s[1][2]=one.s[2][1]=0;
	one.s[1][1]=one.s[2][2]=1;
}
int main(){
	freopen("randoma.in","r",stdin);
	freopen("randoma.out","w",stdout);
	init();
	work();
	return 0;
}