题目链接：Recursive sequence
题意：给出前两项和递推式，求第n项的值。
题解：递推式为：$F[i]=F[i-1]+2*f[i-2]+i^4$
主要问题是$i^4$处理，容易想到用矩阵快速幂，那么$i^4$就需要从$(i-1)$转移过来。
$ i^4 = (i-1)^4 + 4*(i-1)^3 + 6*(i-1)^2 + 4*(i-1) + 1$
$f_i$ $f_{i-1}$ $i^4$ $i^3$ $i^2$ $i$ $1$ = $f_{i-1}$ $f_{i-2}$ $(i-1)^4$ $(i-1)^3$ $(i-1)^2$ $(i-1)$ $1$ *
$\begin{pmatrix}
1 & 1 & 0 & 0 & 0 & 0 & 0 \\
2 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 \\
4 & 0 & 4 & 1 & 0 & 0 & 0 \\
6 & 0 & 6 & 3 & 1 & 0 & 0 \\
4 & 0 & 4 & 3 & 2 & 1 & 0 \\
1 & 0 & 1 & 1 & 1 & 1 & 1 \\
\end{pmatrix}$
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 7
using namespace std; typedef long long ll;
const ll mod=; struct mat
{
ll m[N][N]=
{
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,},
{,,,,,,}
};
}; mat mul(mat a,mat b)
{
mat ans;
int i,j,k;
for(i=;i<N;i++)
for(j=;j<N;j++)
ans.m[i][j]=; for(i=;i<N;i++)
for(j=;j<N;j++)
for(k=;k<N;k++)
ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
return ans;
} ll matpow(int p,ll A,ll B)
{
mat ans,tmp;
int i,j;
for(int i=;i<N;i++)
for(int j=;j<N;j++)
ans.m[i][j]=;
p-=;
ans.m[][]=B;ans.m[][]=A;
ans.m[][]=;ans.m[][]=;ans.m[][]=;ans.m[][]=;ans.m[][]=;
while(p)
{
if(p&) ans=mul(ans,tmp);
tmp=mul(tmp,tmp);
p=p>>;
}
return ans.m[][];
} int main(){
int t;
scanf("%d",&t);
while(t--){
ll M,A,B;
scanf("%lld%lld%lld",&M,&A,&B);
printf("%lld\n",matpow(M,A,B)%mod);
}
return ;
}