题解：

很显然是一道矩阵优化dp

然而表示我很智障地把式子一个个带入

然后就发现了为什么会有那些部分分（大概用扩欧是70吧）

注意用矩阵计算的时候要用快速乘（当然想写高精那也随便，时间无限宽裕）

代码：

#include 
     
      using namespace std;#define ll long longll m,aa,c,x,n,g,mo1;struct re{    ll jz[3][3];}a;ll ksc(ll x,ll y){    if (y==0) return(0);    if (y==1) return(x);    ll tmp=ksc(x,y/2);    tmp=(tmp*2)%mo1;    if (y%2==1) tmp=(tmp+x)%mo1;    return(tmp);}re XX(re x,re y){    re tmp;    memset(tmp.jz,0,sizeof(tmp.jz));    for (ll i=1;i<=2;i++)      for (ll j=1;j<=2;j++)        for (ll k=1;k<=2;k++)          tmp.jz[i][k]+=ksc(x.jz[i][j],y.jz[j][k]),          tmp.jz[i][k]%=mo1;    return(tmp);}re fast_pow(ll x){    if (x==1) return(a);    re b=fast_pow(x/2);    b=XX(b,b);    if (x%2) b=XX(b,a);    return(b);}int main(){    cin>>mo1>>aa>>c>>x>>n>>g;    a.jz[1][1]=aa; a.jz[1][2]=c;    a.jz[2][1]=0; a.jz[2][2]=1;    re cc=fast_pow(n);    ll ans=((ksc(cc.jz[1][1],x)+cc.jz[1][2])%mo1)%g;    cout<