RT，大概率是这个问题

Matrix mul(Matrix A,Matrix B,int p,int q,int s)//p=A的行数，q=B的列数,s=A的列数=B的行数
{
	Matrix Ans;
	memset(Ans.m,0,sizeof(Ans.m));
	for(int i=1;i<=p;++i)
		for(int j=1;j<=q;++j)
			for(int k=1;k<=s;++k)
				Ans.m[i][j]=(Ans.m[i][j]+(A.m[i][k]*B.m[k][j])%p)%p;
	return Ans;
}

以下是完整0分代码（

#include<cstdio>
#include<cstring>
#define int long long
const int p=1000000007;
int t,n;
struct Matrix
{
	int m[10][10];
}A,B,Ans,I;

Matrix mul(Matrix A,Matrix B,int p,int q,int s)
{
	Matrix Ans;
	memset(Ans.m,0,sizeof(Ans.m));
	for(int i=1;i<=p;++i)
		for(int j=1;j<=q;++j)
			for(int k=1;k<=s;++k)
				Ans.m[i][j]=(Ans.m[i][j]+(A.m[i][k]*B.m[k][j])%p)%p;
	return Ans;
}
Matrix qpow(Matrix X,int k,int dim)
{
	Matrix Ans=I,T=X;
	while(k)
	{
		if(k&1) Ans=mul(Ans,T,dim,dim,dim);
		T=mul(T,T,dim,dim,dim);
		k>>=1;
	}
	return Ans;
}

signed main()
{
	A.m[1][1]=1;A.m[1][2]=0;A.m[1][3]=1;
	for(int i=2;i<=3;++i)
			A.m[i][i-1]=1;
	
	B.m[1][1]=B.m[2][1]=B.m[3][1]=1;
	
	for(int i=1;i<=3;++i)
		I.m[i][i]=1;
	
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld",&n);
		Ans=mul(qpow(A,n-3,3),B,3,1,3);
		printf("%lld\n",Ans.m[1][1]%p);
	}
	return 0;
}