样例没过qwq

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n;
void mul(int f[3],int a[3][3]){
	int now[3];
	memset(now,0,sizeof now);
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			now[i]=((now[i]+f[j]*a[i][j]%mod)%mod+mod)%mod;
		}
	}
	memcpy(f,now,sizeof f);
}
void mulself(int a[3][3]){
	int now[3][3];
	memset(now,0,sizeof now);
	for(int i=0;i<3;i++){
		for(int k=0;k<3;k++){
			for(int j=0;j<3;j++){
				now[i][j]=((now[i][j]+a[i][k]*a[j][k]%mod)%mod+mod)%mod;
			}
		}
	}
	memcpy(a,now,sizeof a);
}
void solve(){
	cin>>n;
	if(n<=3){
		cout<<"1\n";
		return;
	}
	n-=3;
	int f[3]={1,1,1};
	int a[3][3]={{1,0,1},{1,0,0},{0,1,0}};
	while(n){
		if(n&1) mul(f,a);
		mulself(a);
		n>>=1;
	}
	cout<<f[0]<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int tt;cin>>tt;while(tt--)solve();
	return 0;
}