显然通过 $X_{i+1}=aX_i+c$ 可以得到 $X_i=\frac{X_{i+1}-c}{a}$ 于是有：

$\left[ \begin{array}{cc|r}X_i &X_{i+1} \\ 0&0\end{array}\right]\times \left[\begin{array}{cc|r}0 & -a \\ 1&A + 1\end{array}\right]=\left[\begin{array}{cc|r}X_{i+1} & aX_{i+2}+c \\ 0&0\end{array}\right]$

但这么写过不了样例，提交只有30分

#include <bits/stdc++.h>
using namespace std;
const long long N=2e8+100;
long long m,a,c,x,n,g;
struct node{
	long long d[5][5],n;
	node I(int p){
		node ret;
		ret.n=p;
		for(int i=1;i<=p;i++){
			for(int j=1;j<=p;j++){
				if(i!=j){
					ret.d[i][j]=0;
				}else{
					ret.d[i][j]=1;
				}
			}
		}
		return ret;
	}
	node friend operator *(node a,node b){
		node ret;
		ret.n=a.n;
		for(int i=1;i<=ret.n;i++){
			for(int j=1;j<=ret.n;j++){
				ret.d[i][j]=0;
				for(int k=1;k<=ret.n;k++){
					ret.d[i][j]=(ret.d[i][j]%m+(a.d[i][k]%m*(b.d[k][j]%m))%m)%m;
				}
			}
		}
		return ret;
	}
}in,base;
node pw(node a,long long e){
	node ret,now=a;ret=ret.I(a.n);
	while(e){
		if(e&1){
			ret=ret*now;
		}
		now=now*now;
		e/=2;
	}
	return ret;
}
int main() {
	ios::sync_with_stdio(0);
	cin>>m>>a>>c>>x>>n>>g;
	base.d[1][1]=x;base.d[1][2]=a*x+c;base.d[2][1]=base.d[2][2]=0;base.n=2;
	in.d[1][1]=0;in.d[2][1]=1;in.d[2][2]=a+1;in.n=2;in.d[1][2]=-a;
	in=pw(in,n);
	base=base*in;
//	for(int i=1;i<=2;i++){
//		for(int j=1;j<=2;j++){
//			cout<<base.d[i][j]<<' ';
//		}cout<<endl;
//	}
	cout<<base.d[1][1]%g<<'\n';
	return 0;
}