记录编号	100533	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	963.[NOI 2012]随机数生成器	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-05-06 10:56:36	内存使用	0.29 MiB

#include<stdio.h>
#define ULL unsigned long long
ULL m,a,c,x0,n,g;
inline ULL sum(ULL x, ULL y){
	if (x + y < m) return x + y;
	else if (x + y == m) return 0;
	return ((x)  + (y) )% m;
}

inline ULL muti(ULL a, ULL b){
	ULL tem = 0;
	if (a <= 100000000 && b <= 1000000000) return (a * b) % m;
	if (a < b) a ^= b ^= a ^= b;
	while (b){
		if (b & 1) tem = (tem + a) % m;
		a <<= 1;
		a %= m;
		b >>= 1;
	}
	return tem;
}

struct martix{
	ULL map[2][2];
	void clean(ULL x,ULL y,ULL z,ULL w){
		map[0][0] = x; map[0][1] = y; map[1][0] = z; map[1][1] = w;
		return;
 	}
	
	inline friend martix operator *(const martix & a,const martix & b){
		martix c;
		c.clean(0LL,0LL,0LL,0LL);
		for (int i = 0; i < 2; i ++)
			for (int k = 0; k < 2; k ++){
				for (int j = 0; j < 2; j++){
					c.map[i][j] = sum(c.map[i][j],muti(a.map[i][k] % m,b.map[k][j] % m));
				}
			}
		return c;
	}
}ans,tem;
int main(){
	freopen("randoma.in","r",stdin);
	freopen("randoma.out","w",stdout);
//	cin >> m >> a >> c >> x0 >> n >> g;
	scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
	tem.clean(a,0LL,c,1LL);
	ans.clean(1LL,0LL,0LL,1LL);
	while (n){
		if (n & 1) ans = tem * ans;
		tem = tem * tem;
		n >>= 1;
	}
	tem.clean(x0,1,0,0);
	tem = tem * ans;
	tem.map[0][0] %= g;
	//cout << tem.map[0][0] << endl;
	printf("%lld\n",tem.map[0][0]);
	return 0;
}