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,abfcn−1fn−2,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.

1≤T≤10,1≤n≤1018,1≤a,b,c≤109,p is a prime number,and p≤109+7.

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

Sample Input 1 5 3 3 3 233

Sample Output 190

用矩阵快速幂的时候，注意对p-1取余 递推式：a[n]=c*a[n-1]+a[n-2]+1;

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;
typedef long long int LL;
struct Node
{
    LL a[3][3];
}A,B,C;
LL p,n,a,b,c;
Node multiply(Node a,Node b)
{
    Node 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;
}
Node get(Node a,LL x)
{
    Node c;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
             c.a[i][j]=(i==j?1:0);
    for(x;x;x>>=1)
    {
        if(x&1) c=multiply(c,a);
        a=multiply(a,a);
    }
    return c;
}
LL quick(LL x,LL y)
{
    if(n>1&&y==0) y=p-1;
    LL ans=1;
    for(y;y;y>>=1)
    {
        if(y&1)  ans=(ans*x)%p;
        x=(x*x)%p;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&p);
        A.a[0][0]=0;A.a[1][0]=0;A.a[2][0]=1;
        B.a[0][0]=c; B.a[0][1]=1; B.a[0][2]=1;
        B.a[1][0]=1; B.a[1][1]=0; B.a[1][2]=0;
        B.a[2][0]=0; B.a[2][1]=0; B.a[2][2]=1;
        if(n==1) {cout<<1<<endl;continue;}
        B=get(B,n-1);
        B=multiply(B,A);
        LL num=((B.a[0][0]%(p-1))*(b%(p-1)))%(p-1);
        //cout<<num<<endl;
        cout<<quick(a,num)<<endl;
    }
    return 0;
}