#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long ll;

const ll mod=1000000007;

struct Matrix{
	ll n,m,a[110][110];
	Matrix():n(0),m(0){}
	Matrix(int N,int M,bool f=0):n(N),m(M){
		memset(a,0,sizeof a);
		if(f)for(int i=1;i<=n;++i)a[i][i]=1;
	}
	const friend Matrix operator*(Matrix& lhs,Matrix& rhs){
		Matrix ans(lhs.n,rhs.m);
		for(int i=1;i<=lhs.n;++i){
			for(int j=1;j<=rhs.m;++j){
				for(int k=1;k<=lhs.m;++k)ans.a[i][j]=(ans.a[i][j]+lhs.a[i][k]*rhs.a[k][j])%mod;
			}
		}
		return ans;
	}
	friend Matrix operator*=(Matrix& lhs,Matrix rhs){
		return lhs=lhs*rhs;
	}
	friend Matrix pow(Matrix& a,ll exp){
		Matrix ans(a.n,a.n,1);
		while(exp){
			if(exp&1)ans*=a;
			a*=a;
			exp>>=1;
		}
		return ans;
	}
	friend istream& operator>>(istream &is,Matrix& m){
		for(int i=1;i<=m.n;++i){
			for(int j=1;j<=m.m;++j)is >> m.a[i][j];
		}
		return is;
	}
	friend ostream& operator<<(ostream &os,const Matrix& m){
		for(int i=1;i<=m.n;++i){
			for(int j=1;j<=m.m;++j)os << m.a[i][j] << " \n"[j==m.m&&i!=m.n];
		}
		return os;
	}
};
ll t,n;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--){
		Matrix base(3,3),ans(3,1);
		cin >> n;
		if(n<=3){
			cout << 1 << endl;
			return 0;
		}
		base.a[1][1]=base.a[1][3]=base.a[2][1]=base.a[3][2]=1;
		ans=pow(base,n-1);
		cout << ans.a[1][1] << endl;
	}
	return 0;
}

评测寄录

然鹅，下载了数据用文件读写了之后甚至fc过了，未找到不同。