rt，样例没有过，输出全是 $0$。

码风较丑，不要在意。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1e9+7;
const ll N=10;
ll n,k,T;
struct node{ 
  ll x[N][N];
}base,ans;
node operator * (const node &a,const node &b){
    node anss;
    memset(anss.x,0,sizeof(anss.x));
    for(ll k=1;k<=3;k++)
        for(ll i=1;i<=3;i++)
            for(ll j=1;j<=3;j++){
                anss.x[i][j]=(anss.x[i][j]+a.x[i][k]*b.x[k][j]%MOD)%MOD;
            }
    return anss;
}
int main(){
cin>>T;
while(T--){
	cin>>n;
    if(n<=3){
        cout<<1<<endl;continue;
    }
    node ans,base;
    memset(ans.x,0,sizeof(ans.x));
    ans.x[1][1]=ans.x[2][2]=ans.x[3][3]=1; 
    memset(base.x,0,sizeof(base.x));
    base.x[1][1]=base.x[2][1]=base.x[1][3]=base.x[3][2]=1;
    while(k){
        if(k&1) ans=ans*base;
        base=base*base;
        k>>=1;
    }
    cout<<ans.x[2][1]<<endl;
}
	return 0;
}