#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N=1e5+50;
const int M=1e5+50;
const int Mod=1e9+7;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

struct Matrix{
    ll a[4][4];
    Matrix(){memset(a,0,sizeof(a));}
    Matrix operator *(const Matrix& b)const{
        Matrix res;
        for(int i=1;i<=3;++i){
            for(int j=1;j<=3;++j){
                for(int k=1;k<=3;++k){
                    res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[j][k])%Mod;
                }
            }
        }
        return res;
    }
}A,B;

int t,n;

void qbow(int k){
    while(k){
        if(k&1) B=B*A;
        A=A*A;
        k>>=1;
    }
}

int main()
{
    t=read();
    while(t--){
        n=read();
        if(n<=3){
            printf("1\n");
            continue;
        }
        memset(A.a,0,sizeof(A.a));
        memset(B.a,0,sizeof(B.a));  
        for(int i=1;i<=3;++i) B.a[i][i]=1;
        A.a[1][1]=A.a[3][1]=A.a[1][2]=A.a[2][3]=1;
        qbow(n-1);
        printf("%lld\n",B.a[1][1]);
    }
    return 0;
}