题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5667
费马小定理：
假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p）。
即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
注意这里使用快速幂的时候要根据费马小定理对p-1取模。还有注意a%p=0的情况。
递推式：f(n)=f(n-1)*c+f(n-2)+1 非齐次。
构造矩阵：
|c |
| |
| |
初始的矩阵：
||
||
||
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; typedef long long ll;
const ll maxn = ;
ll n, a, b, c, p; typedef struct Matrix {
ll m[maxn][maxn];
ll r;
ll c;
Matrix(){
r = c = ;
memset(m, , sizeof(m));
}
} Matrix; Matrix mul(Matrix m1, Matrix m2, ll mod) {
Matrix ans = Matrix();
ans.r = m1.r;
ans.c = m2.c;
for(ll i = ; i <= m1.r; i++) {
for(ll j = ; j <= m2.r; j++) {
for(ll k = ; k <= m2.c; k++) {
if(m2.m[j][k] == ) continue;
ans.m[i][k] = ((ans.m[i][k] + m1.m[i][j] * m2.m[j][k] % mod) % mod) % mod;
}
}
}
return ans;
} Matrix quickmul(Matrix m, ll n, ll mod) {
Matrix ans = Matrix();
for(ll i = ; i <= m.r; i++) {
ans.m[i][i] = ;
}
ans.r = m.r;
ans.c = m.c;
while(n) {
if(n & ) {
ans = mul(m, ans, mod);
}
m = mul(m, m, mod);
n >>= ;
}
return ans;
} ll qm(ll x, ll n, ll mod) {
ll ans = , t = x;
while(n) {
if(n & ) ans = (ans * t) % mod;
t = (t * t) % mod;
n >>= ;
}
return ans;
}
int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
cin >> n >> a >> b >> c >> p;
Matrix r;
r.r = , r.c = ;
r.m[][] = ;
r.m[][] = ;
r.m[][] = ;
if(n == ) {
printf("1\n");
continue;
}
if(n == ) {
printf("%I64d\n", qm(a, b, p));
continue;
}
if(a % p == ) {
printf("0\n");
continue;
}
Matrix s;
s.r = s.c = ;
s.m[][] = c, s.m[][] = , s.m[][] = ;
s.m[][] = , s.m[][] = , s.m[][] = ;
s.m[][] = , s.m[][] = , s.m[][] = ;
s = quickmul(s, n-, p-);
ll ans = ;
for(int i = ; i <= r.r; i++) {
ans = (ans + (s.m[][i] * r.m[i][]) % (p - )) % (p - );
}
printf("%I64d\n", qm(a, (ans*b)%(p-), p));
}
return ;
}