先讲想法：蒟蒻的矩阵构造代码里有，蒟蒻想着已经有了a1,a2,a3，那么直接做（n-3）次矩阵左乘，然后答案在A.a[0][0]*a1+A.a[0][2]*a3，其中a1,a3都是1，可是最后答案错了，debug时意外发现AC代码，求助大佬蒟蒻思路上的错误在哪，贴AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int t,n;
struct Matrix{
	int a[3][3]={{1,0,1},
				 {1,0,0},
				 {0,1,0}};
	friend Matrix operator *(Matrix o,Matrix p ){
		Matrix ans;
		memset(ans.a,0,sizeof ans.a); 
		for(int i=0;i<3;++i)
			for(int j=0;j<3;++j)
				for(int k=0;k<3;++k)
					(ans.a[i][j]+=o.a[i][k]*p.a[k][j]%mod)%=mod;
		return ans;
	}
	Matrix operator^(int k){
		--k;
		Matrix ans=*this,A=*this;
		while(k){
			if(k&1)ans=ans*A;
			k>>=1;
			A=A*A;
		}
		return ans;
	}
};
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		if(n>=1&&n<=3){
			cout<<1<<"\n";
			continue;
		}
		Matrix A;
		A=A^(n-1);
		//for(int i=0;i<3;++i)for(int j=0;j<3;++j)cout<<A.a[i][j]<<" \n"[j==2];
		cout<<(A.a[0][0])%mod<<"\n";
	}
	return 0;
}