题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5667

题意：

Lcomyn 是个很厉害的选手,除了喜欢写17kb+的代码题,偶尔还会写数学题.他找到了一个数列:

fn=

给定各个数，求fn。

分析：

可以发现最后都是a的倍数，这样我们让fn对a取对数，令tn=logafn方程就转化为b+ctn−1+tn−2，这样利用矩阵快速幂直接算幂数，最后快速幂一下就可以了。

注意：

• 由费马小定理可知，ab%p=ab/(p−1)∗(p−1)+b%(p−1)%p=ab/(p−1)∗(p−1)%p∗ab%(p−1)%p=ab%(p−1)%p，所以矩阵快速幂的模应该为p−1。
• 特别注意a%p==0的时候，答案应该为0。

代码：

#include<cstdio>

const int N = 105;

int mod = 1e9 + 7;

struct Matrix

{

    int row,cal;

    long long  m[N][N];

};

Matrix init(Matrix a, long long t)

{

    for(int i = 0; i < a.row; i++)

        for(int j = 0; j < a.cal; j++)

            a.m[i][j] = t;

    return a;

}

Matrix mul(Matrix a,Matrix b)

{

    Matrix ans;

    ans.row = a.row, ans.cal = b.cal;

    ans = init(ans,0);

    for(int i = 0; i < a.row; i++)

        for(int j = 0; j < b.cal; j++)

            for(int k = 0; k < a.cal; k++)

                ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j])%mod;

    return ans;

}

int quickpow(int a, int b, int mod)

{

    int ans = 1;

    for(;b;b >>= 1, a = a * 1ll * a % mod){

        if(b & 1) ans = ans * 1ll * a % mod;

    }

    return ans;

}

int quick_pow(long long k, int b, Matrix A)

{

    if(k < 0) return 0;

    if(k == 0) return b;

    Matrix I;

    I.row = 3, I.cal = 1;

    I = init(I, 0);

    I.m[0][0] = 1;

    I.m[1][0] = b;

    I.m[2][0] = 0;

    while(k){

        if(k & 1) I = mul(A, I);

        A = mul(A, A);

        k>>=1;

    }

    return I.m[1][0]%mod;

}

int main (void)

{

    int T;scanf("%d", &T);

    while(T--){

        int a, b, c, p;

        long long n;

        scanf("%I64d%d%d%d%d", &n, &a,&b, &c, &p);

        if(a % p == 0){printf("0\n");continue;}

        mod = p - 1;

        Matrix A;

        A.row = 3, A.cal = 3;

        A = init(A, 0);

        A.m[0][0] = A.m[2][1] = A.m[1][2] = 1;

        A.m[1][0] = b;A.m[1][1] = c;

        int res = quick_pow(n - 2, b, A);

        printf("%d\n", quickpow(a, res, p));

    }

}