本地测完全正确,真的很离谱

10
39
20
39
38
56
98
66
86
51
13

1243524
872
1243524
848491
825604416
795935567
743426048
369866299
122106097
60

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
const int P=1e9+7;
int T,n;

namespace mat {
	const int L=5,C=5;
	ll cge[L][C]={{0,1,0},{0,0,1},{1,0,1}};
	ll ans[L][C];
	void cpy(ll a[L][C],ll b[L][C]) {
		for(ll i=0;i<L;i++) 
			for(ll j=0;j<C;j++) 
				a[i][j]=b[i][j];
	}
	void cal(ll a[L][C],ll b[L][C],ll to[L][C],int l,int c) {
		ll t[L][C];
		for(int i=0;i<l;i++) {
			for(int j=0;j<c;j++) {
				ll res=0;
				for(int k=0;k<L;k++) res=(res+a[k][i]*b[j][k])%P;
				t[j][i]=res;
			}
		}
		cpy(to,t);
	}
	void pow(int x) {
		ll t[L][C]={{1,0,0},{0,1,0},{0,0,1}};
		cpy(ans,t);
		cpy(t,cge);
		while(x) {
			if(x&1) cal(t,ans,ans,3,3);
			x>>=1;
			cal(t,t,t,3,3);
		}
	}
}

int main() {
	ll t[5][5]={{1},{1},{1}};
	for(scanf("%d",&T);T;T--) {
		scanf("%d",&n);
		if(n<=3) printf("1\n");
		else {
			mat::pow(n-3);
			mat::cal(t,mat::ans,mat::ans,1,3);
			printf("%lld\n",mat::ans[2][0]%P);
		}
	}
	
    return 0;
}