#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1e9 + 7;

struct mat {
    int a[10][10];
    mat() {
        memset(a, 0, sizeof a);
    }
};

int n;
mat I;

mat operator * (mat A, mat B) {
    mat C;

    for (int i = 1; i <= 3; i ++)
        for (int j = 1; j <= 3; j ++)
            for (int k = 1; k <= 3; k ++)
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;

    return C;
}

mat qpow(mat x, int y) {
    mat ret = I;

    while (y) {
        if (y & 1)
            ret = ret * x;

        x = x * x;
        y >>= 1;
    }

    return ret;
}

void solve() {
    cin >> n;
    mat A;
    A.a[1][1] = A.a[2][2] = A.a[3][3] = 1;

    if (n <= 3)
        cout << 1 << endl;
    else
    {
        mat A = qpow(A, n);
        cout << A.a[2][1] << endl;
    }
    return ;
}

signed main() {
    I.a[1][1] = I.a[2][1] = I.a[1][3] = I.a[3][2] = 1;
    int T;
    cin >> T;

    while (T --)
        solve();

    return 0;
}