远古NOI题。

第一眼看过去，似乎是线性递推。
注意到数据范围中 $n \leq 10^{18}$，$O(n)$ 算法不可行，考虑 $O(\log(n))$ 算法。
矩阵乘法满足结合律，所以矩阵乘法可以通过快速幂的思想优化，即矩阵快速幂。
而众所周知，线性递推可以用矩阵乘法表示。
注意到：

$$\begin{bmatrix} X_i&c \end{bmatrix} \begin{bmatrix} a&0\\1&1 \end{bmatrix}= \begin{bmatrix} X_{i+1}&c \end{bmatrix}$$

则

$$\left( \begin{bmatrix} X_0&c \end{bmatrix} \begin{bmatrix} a&0\\1&1 \end{bmatrix}^n \right)_{1,1} \bmod{g}$$

即为所求。

几个坑点：

• 要开 __int128 或用龟速乘；
• 先模 $m$ 再模 $g$。

上AC代码：（提交记录）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=107;
char c;
ll k,g;
__int128 a[64][N][N],p[N][N],ans[N][N],tmp[N][N],mod;
//矩阵乘法
void MUL(int r,int s,int t,__int128 x[N][N],__int128 y[N][N],__int128 (&res)[N][N]){
	for(int i=1;i<=r;i++){
		for(int k=1;k<=t;k++){
			tmp[i][k]=x[i][k];
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++){
			res[i][j]=0;
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++){
			for(int k=1;k<=t;k++){
				res[i][j]=(res[i][j]+tmp[i][k]*y[k][j])%mod;
			}
		}
	}
	return;
}
//输入128位整数
__int128 rd(){
	__int128 tmp=0,k=1;
	while(!isdigit(c)){
		if(c=='-') k=-k;
		c=getchar();
	}
	while(isdigit(c)){
		tmp=10*tmp+c-'0';
		c=getchar();
	}
	tmp*=k;
	return tmp;
}
//输出128位整数
void wr(__int128 x){
	if(x<0) printf("-");
	int f=0;
	__int128 tmp=1;
	for(int i=1;i<=30;i++) tmp*=10;
	for(int i=30;i>=0;i--){
		if(f||(x/tmp%10)>0){
			printf("%c",(int)(x/tmp%10+'0'));
			f=1;
		}
		tmp/=10;
	}
	if(!f) printf("0");
	printf(" ");
	return;
}
int main(){
	mod=rd();
	a[0][1][1]=rd();
	ans[1][2]=rd();
	ans[1][1]=rd();
	a[0][2][1]=a[0][2][2]=1;
	cin>>k>>g;
	for(int h=0;h<=60;h++){
    //迭代式矩阵快速幂
		if(k&(1ll<<h)) MUL(1,2,2,ans,a[h],ans);
		MUL(2,2,2,a[h],a[h],a[h+1]);
	}
	cout<<(ll)(ans[1][1]%g);
	return 0;
}