感觉柿子推的没问题……

//2023/7/26
//别着急，先通读一遍题目
//别忘了开long long
//写完先看一遍怎么降复杂度
//要么开全局变量要么给定初值
//想想看，有什么情况需要特判
//看看数组开的够不够大
//std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MAXN=1e3+10;
const int MOD=1e9+7;
int n,k;
struct juz{
	int a[3][3];
	juz(){memset(a,0,sizeof(a));}
	void build(){
		for (int i=1;i<=n;i++) a[i][i]=1;
	}
	juz friend operator * (juz &x,juz &y){
		juz t;
		for (int i=0;i<3;i++){
			for (int k=0;k<3;k++){
				for (int j=0;j<3;j++){
					t.a[i][j]=(t.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;
				}
			}
		}
		/*for (int i=0;i<3;i++){
			cout<<t.a[i][0]<<" ";
		}
		cout<<endl;*/
		return t;
	}
}data;
juz ans;
void init()
{
	data.a[0][0]=data.a[2][0]=data.a[0][1]=data.a[1][2]=1;
 	ans.a[0][0]=ans.a[0][1]=ans.a[0][2]=1;
}
void qpow(int k)
{
	while(k>0){
		if(k&1)	ans=ans*data;
		data=data*data;
		k>>=1;
	}
}
signed main()
{
	int t;
	cin>>t;
	while(t--){
		cin>>n; 
		if(n<=3){
			cout<<"1"<<endl;
			continue;
		}
		init();
		qpow(n-3);
		cout<<ans.a[0][0]<<endl;
	}
	return 0;
}