【模板】矩阵加速（数列） - 洛谷
【模板】矩阵快速幂 - 洛谷
哇啦哇啦，矩阵快速幂其实就是快速幂+矩阵乘法；
矩阵加速则是如斐波那契数列这样的递推式的快速求法，关键在构造出相应的矩阵帮助求解；
献上大佬博文：矩阵构造方法 - jumpingfrog0 - 博客园
接下来就没什么好说的了QwQ
带板子：
/*keep on going and never give up*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
inline int read()
{int x=0,k=1; char c=getchar();while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;
}
const double E = exp(1);
const double PI = acos(-1.0);
const int maxn=4e5+10;
const int mod=1e9+7;
int n,k;
struct Matrix{int c[101][101];
}a,ans;//I:同ans、
struct Matrix operator*(const Matrix &x,const Matrix &y){Matrix tep;for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)tep.c[i][j]=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++){tep.c[i][j]+=x.c[i][k]*y.c[k][j]%mod;tep.c[i][j]%=mod;}return tep;
}
signed main() {n=read(),k=read();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) a.c[i][j]=read();for(int i=1;i<=n;i++) ans.c[i][i]=1;//单位矩阵。 while(k){if(k&1) ans=ans*a; a=a*a;k=k>>1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) cout<<ans.c[i][j]<<" ";cout<<"\n";}
} /*keep on going and never give up*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
inline int read()
{int x=0,k=1; char c=getchar();while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;
}
const double E = exp(1);
const double PI = acos(-1.0);
const int maxn=4e5+10;
const int Mod=1e9+7;
typedef long long LL;
int T, n;
struct mat{LL m[5][5];
}Ans, base;
inline void init() {memset(Ans.m, 0, sizeof(Ans.m));for(int i=1; i<=3; i++) Ans.m[i][i] = 1;memset(base.m, 0, sizeof(base.m));base.m[1][1] = base.m[1][3] = base.m[2][1] = base.m[3][2] = 1;
}
inline mat mul(mat a, mat b) {mat res;memset(res.m, 0, sizeof(res.m));for(int i=1; i<=3; i++) {for(int j=1; j<=3; j++) {for(int k=1; k<=3; k++) {res.m[i][j] += (a.m[i][k] % Mod) * (b.m[k][j] % Mod);res.m[i][j] %= Mod;}}}return res;
}
inline void Qmat_pow(int p) {while (p) {if(p & 1) Ans = mul(Ans, base);base = mul(base, base);p >>= 1;}
}signed main() {scanf("%d", &T);while (T--) {scanf("%d", &n);if(n <= 3) {printf("1\n");continue;}init();Qmat_pow(n);printf("%lld\n", Ans.m[2][1]);}
}