Problem Description
    Holion August will eat every thing he has found.

    Now there are many foods,but he does not want to eat all of them at once,so he find a sequence.

fn=1,ab,abfcn1fn2,n=1n=2otherwise

    He gives you 5 numbers n,a,b,c,p,and he will eat  fn foods.But there are only p foods,so you should tell him  fn mod p.
 

Input
    The first line has a number,T,means testcase.

    Each testcase has 5 numbers,including n,a,b,c,p in a line.

    1T10,1n1018,1a,b,c109, p is a prime number,and  p109+7.
 

Output
    Output one number for each case,which is  fn mod p.
 

Sample Input
1 5 3 3 3 233
 

Sample Output
190

把次数拿下来就可以用矩阵递推了,要注意会有a%p=0的情况

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n,a,b,c,p;
int T;
struct Matrix{
   LL a[3][3];
}A,B;//A,初始矩阵,B,构造矩阵

Matrix operator*(const Matrix&a,const Matrix&b)//矩阵乘法加费马小定理
{
    Matrix c;
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            c.a[i][j]=0;
            for(int k=0; k<3; k++)
            {
                (c.a[i][j]+=a.a[i][k]*b.a[k][j]%(p-1))%=(p-1);
            }
        }
    }
    return c;
}
Matrix pow(Matrix a,LL x)
{
    Matrix c;
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            if(i==j)c.a[i][j]=1;
            else c.a[i][j]=0;
        }
    }
    while(x)
    {
        if(x&1) c=c*a;
        a=a*a;
        x>>=1;
    }
    return c;
}
//LL get(LL x,LL y)
//{
//    LL res=x;
//    while(y)
//    {
//        if(y&1)res=(res*x)%p;
//        x=((x%p)*(x%p))%p;
//        y>>=1;
//    }
//    return res;
//}
LL powmod(LL a,LL b,LL c)
{
    if(b==0)b=c-1;//没有这句话,会WA.
    LL ans=1;
    while (b)
    {
        if (b%2==1) ans=ans*a%c;
        b/=2;
        a=a*a%c;
    }
    return ans;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        cin>>n>>a>>b>>c>>p;
        A.a[0][0]=0,A.a[0][1]=b,A.a[0][2]=b;
        B.a[0][0]=0,B.a[0][1]=1,B.a[0][2]=0;
        B.a[1][0]=1,B.a[1][1]=c,B.a[1][2]=0;
        B.a[2][0]=0,B.a[2][1]=1,B.a[2][2]=1;
        if(n==1){printf("1\n");continue;}
        B = pow(B,n-2);
        A = A*B;
        LL ans = powmod(a,A.a[0][1],p);
        cout<<ans<<endl;
    }
    return 0;
}