mxqz矩阵加速

#include<bits/stdc++.h>
using namespace std;
#define int __int128
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')
        {
            w=-1;
        }
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        s=s*10+(ch-'0');
        ch=getchar();
    }
    return s*w;
}
void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x<10)
    {
        putchar(x%10+'0');
        return ;
    }
    print(x/10);
    putchar(x%10+'0');
}
int m,a,c,X0,n,g;
struct Matrix{
    int mat[3][3];
    Matrix(){memset(mat,0,sizeof(mat));}
}bat;

Matrix mul(Matrix a,Matrix b)
{
    Matrix res;
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            for(int k=1;k<=2;k++)
            {
                res.mat[i][j]=(res.mat[i][j]+a.mat[i][k]*b.mat[k][j])%m;
            }
        }
    }
    return res;
}
Matrix qpow(Matrix a,int b)
{
    Matrix res=bat;
    while(b)
    {
        if(b&1)
        {
            res=mul(res,a);
        }
        a=mul(a,a);
        b>>=1;
    }
    return res;
}
signed main()
{
    m=read();
    a=read();
    c=read();
    X0=read();
    n=read();
    g=read();
    if(n==0)
    {
        print(X0%g);
        return 0;
    }
    X0%=m;
    bat.mat[1][1]=X0;
    bat.mat[2][1]=c;
    Matrix Mul;
    Mul.mat[1][1]=a;
    Mul.mat[1][2]=1;
    Mul.mat[2][2]=1;
    bat=qpow(Mul,n);
    int ans=bat.mat[1][1]%g;
    print(ans);
    return 0;
}