RT，感觉思路没什么问题 (逃

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

const int MOD=1e9+7;
const int N=3;//阶

struct Mar
{
	ll m_[N][N];
};

Mar operator*(const Mar &x,const Mar &y)//矩阵乘法
{
	Mar tmp;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			tmp.m_[i][j]=0;
		}
	}
	
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			for(int k=0;k<N;k++)
			{
				tmp.m_[i][j]+=x.m_[i][k]*y.m_[k][j]%MOD;
				tmp.m_[i][j]%=MOD;
			}
		}
	}
	return tmp;
}

ll bts[N][N]={
	{1,1,0},
	{0,0,1},
	{1,0,0}
};

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	Mar A,F;
	
	ll t;
	cin>>t;
	while(t--)
	{
		memset(F.m_,0,sizeof F.m_);
		F.m_[0][0]=F.m_[0][1]=F.m_[0][2]=1;
		memcpy(A.m_,bts,sizeof bts);//初始化
		
		ll n;
		cin>>n;
		if(n<=3)
		{
			puts("1"); continue;
		}
		else n-=3;//需要乘的次数
		
		while(n)
		{
			if(n&1) F=F*A;
			A=A*A;
			n>>=1;
		}
		
		cout<<F.m_[0][0]<<endl;
	}
	return 0;
}