官方题解：
观察递推式我们可以发现，所有的fi都是a的幂次，所以我们可以对fi取一个以a为底的log，gi=loga fi
那么递推式变gi=b+c∗gi−1+gi−2,这个式子可以矩阵乘法
这题有一个小trick，注意a mod p=0的情况.
分析：排除了a mod p=0的情况，幂次可以对（p-1)取模，这是由于离散对数定理
相关定理请查阅 算导
吐槽：比赛的时候就是被a mod p=0这种情况给hack掉了，我太弱了
#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <string.h>
#include <string>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=1e5+;
LL p,a,b,c,n;
struct asd{
LL c[][];
};
asd mul(asd a,asd b){
asd d;
for(int i=;i<=;++i){
for(int j=;j<=;++j){
d.c[i][j]=;
for(int k=;k<=;++k)
d.c[i][j]=(d.c[i][j]+a.c[i][k]*b.c[k][j]%(p-))%(p-);
}
}
return d;
}
asd fun(LL m){
asd a,e;
for(int i=;i<=;++i)
for(int j=;j<=;++j)
a.c[i][j]=e.c[i][j]=;
a.c[][]=c;
a.c[][]=;
a.c[][]=b;
a.c[][]=;
a.c[][]=;
e.c[][]=e.c[][]=e.c[][]=;
while(m){
if(m&)e=mul(e,a);
m>>=;
a=mul(a,a);
}
return e;
}
LL fun2(LL a,LL x){
LL res=;
while(x){
if(x&)res=(res*a)%p;
x>>=;
a=(a*a)%p;
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%I64d%I64d%I64d%I64d%I64d",&n,&a,&b,&c,&p);
if(n==){
printf("1\n");
continue;
}
if(n==){
printf("%I64d\n",fun2(a,b));
continue;
}
if(a%p==){
printf("0\n");
continue;
}
asd t=fun(n-);
LL x=;
x=(x+t.c[][]*b%(p-))%(p-);
x=(x+t.c[][])%(p-);
printf("%I64d\n",fun2(a,x));
}
return ;
}