样例没过

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n;
struct nod
{
	long long bp[4][4],op[4][4];
	inline void build()
	{
		memset(bp,0,sizeof(bp));
		for(int i=1;i<=3;i++)
			bp[i][i]=1;
	}
}qa,ans;
nod operator *(const nod &a,const nod &b)
{
	nod res;
	for(int k=1;k<=3;k++)
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
				res.bp[i][j]=(res.bp[i][j]+a.bp[i][k]%mod*b.op[k][j]%mod)%mod;
	return res;
}
nod ksm(nod w,long long k)
{
	while(k)
	{
		if(k&1)
			ans=ans*w;
		w=w*w;
		k>>=1;
	}
	return ans;
}
int main()
{
 	int t;
	cin>>t;
	while(t--)
	{
		qa.op[1][1]=qa.op[1][3]=qa.op[2][1]=qa.op[3][2]=1;
		memset(ans.bp,0,sizeof(ans.bp));
		ans.build();
		cin>>n;
		if(n<=3)
		{
			cout<<1<<endl;
			continue;
		}
		ans=ksm(qa,n);
//		for(int i=1;i<=3;i++)
//			for(int j=1;j<=n;j++)
//				cout<<ans.bp[i][j]<<endl;
		cout<<ans.bp[2][1]<<endl;
	 } 
	return 0;
}