学步园

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL __int64
LL a,b,n,m;
void Mul(LL mat1[2][2],LL mat2[2][2],LL mat[2][2])
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        {
            LL sum=0;
            for(int k=0;k<2;k++)
                sum+=(mat1[i][k]*mat2[k][j])%m;
            mat[i][j]=sum%m;
        }
}
void Pow(LL mat[2][2],LL k)
{
    if(k==1) return ;
    LL mat1[2][2],mat2[2][2];
    memcpy(mat1,mat,sizeof(mat1));
    Pow(mat1,k>>1);
    if(k&1)
    {
        Mul(mat1,mat,mat2);
        Mul(mat2,mat1,mat);
    }
    else
        Mul(mat1,mat1,mat);
}
int main()
{

    while(cin>>a>>b>>n>>m)
    {
        if(n==0)
        {
            printf("2\n");continue;
        }
            
        if(n==1)
        {
            printf("%I64d\n",2*a%m);continue;
        }
            
        if(n==2)
        {
            printf("%I64d\n",(2*a*a%m+2*b)%m);continue;
        }
            
        LL mat[2][2];
        mat[0][0]=2*a;   mat[0][1]=((b-a*a)%m+m)%m;
        mat[1][0]=1;     mat[1][1]=0;
        Pow(mat,n);
        printf("%I64d\n",(mat[1][0]*2*a+mat[1][1]*2)%m);
    }
    return 0;
}