#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
inline int read()
{
    char s = 'r';
    int res = 0;
    int f = 1;
    while(!isdigit(s)){
        if(s == '-') f = -1;
        s = getchar();
    }
    while(isdigit(s)){
        res = (res * 10 + s - '0') % mod;
        s = getchar();
    }
    return res * f;
}
void write(int x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}
inline void write(char s){
    putchar(s);
}
struct Matrix
{
    int n,m;
    int mat[105][105];
    Matrix(const int &a,const int &b){
        n = a;
        m = b;
        memset(mat,0,sizeof(mat));
    }

    // void read_this(){
    //     for(int i = 1; i <= this->n; i ++ ){
    //         for(int j = 1; j <= this->m; j ++ ){
    //             mat[i][j] = read();
    //         }
    //     }
    // }
    // void print(){
    //     for(int i = 1; i <= this->n; i ++ ){
    //         for(int j = 1; j <= this->m; j ++ ){
    //             write(this->mat[i][j]);
    //             write(' ');
    //         }
    //         write('\n');
    //     }
    // }
};
Matrix mul(const Matrix &a,const Matrix &b){
    Matrix ans(a.n,b.m);
    for(int i = 1; i <= ans.n; i ++ ){
        for(int j = 1; j <= ans.m; j ++ ){
            for(int k = 1; k <= a.m; k ++ ){
                ans.mat[i][j] = (ans.mat[i][j] + a.mat[i][k] * b.mat[k][j] % mod) % mod;
            }
        }
    }
    return ans;
}
int n,k;
Matrix fpow(Matrix x,long long p){
    Matrix res(x.n,x.n);
    for(int i = 1; i <= x.n; i ++ ){
        res.mat[i][i] = 1;
    }
    while(p){
        if(p & 1) 
            res = mul(res,x);        
        p >>= 1;
        x = mul(x , x);
    } 
    return res;
}
signed main()
{
    Matrix bas(3,3),ori(3,1);
    bas.mat[1][1] = bas.mat[2][1] = bas.mat[3   ][2] = bas.mat[1][3] = 1;
    ori.mat[1][1] = ori.mat[2][1] = ori.mat[3][1] = 1;
    int T = read();
    while(T--){
        n = read();
        if(n <= 3) {
            write('1');
            write('\n');
            continue;
        }
        Matrix ans = fpow(bas,n - 3);
        ans = mul(ans, ori);
        write(ans.mat[1][1]);
        write('\n');
    }
}