矩阵快速幂，这样写在 $T=2000,n=10^{18}$ 的时候会超时，求卡常/kel

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007ll
int T,n,i,j,k,s;
struct evmatrix
{
	int t[10][10];
} a,sto_zmz_orz;
evmatrix mul(evmatrix a,evmatrix b)
{
	evmatrix c;
	memset(c.t,0,sizeof(c.t));
	for(int i=1;i<=9;i++)
		for(int k=1;k<=9;k++)
			for(int j=1;j<=9;j++)
				c.t[i][j]=(c.t[i][j]+a.t[i][k]*b.t[k][j]%mod)%mod;
	return c;
}
void ksm(int mc,evmatrix a)
{
	evmatrix b;s=0;
	memset(b.t,0,sizeof(b.t));
	for(int i=1;i<=9;i++) b.t[i][i]=1;
	while(mc)
	{
		if(mc&1)b=mul(a,b);
		mc>>=1;a=mul(a,a);
	}
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++) s=(s+b.t[i][j])%mod;
}
signed main()
{
	scanf("%lld",&T);
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			for(k=0;k<3;k++)
				if(i*k<=j*j)sto_zmz_orz.t[i*3+j+1][j*3+k+1]=1;
	while(T--)
	{
		scanf("%lld",&n);
		for(i=1;i<=9;i++)
			for(j=1;j<=9;j++) a.t[i][j]=sto_zmz_orz.t[i][j];
		ksm(n-2,a);
		printf("%lld\n",s);
	}
	return 0;
}