rt，开了O2会全部WA掉，原因是输出过短

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p=1e9+7,T;
struct node{
	int a[5][5];
	int r,c;
	node(){memset(a,0,sizeof(a));}
};
node p0,a0;
node mul(node x,node y){
	node t;
	for(int i=1;i<=x.r;i++){
		for(int j=1;j<=y.c;j++){
			for(int k=1;k<=x.c;k++){
				t.a[i][j]+=x.a[i][k]*y.a[k][j];
				t.a[i][j]%=p;
			}
		}
	}
	t.r=x.r,t.c=y.c;
	return t;
}
void ksm(int b) { 
    while(b){
        if (b&1)p0=mul(p0,a0);
        a0=mul(a0,a0);
        b>>=1;
    }
}
void init(){
	a0.a[1][1]=1;
	a0.a[2][1]=1;
	a0.a[1][3]=1;
	a0.a[3][2]=1;
	p0.a[1][1]=1;
	p0.a[1][2]=1;
	p0.a[1][3]=1;
	p0.r=1,p0.c=3;
	a0.r=3,a0.c=3;
}
signed main(){
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);
		if(n<=3){
			cout<<"1\n";
			continue;
		}
		for(int i=1;i<=5;i++){
			for(int j=1;j<=5;j++){
				a0.a[i][j]=0;
				p0.a[i][j]=0;
			}
		}
		init();
		ksm(n-3);
		cout<<p0.a[1][1]<<"\n";
	}
	return 0;
}