#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <cassert>
#include <cmath>
using namespace std;
#define int long long
#define SZ(c) (int)(c.size())

vector<int> dummy_zero;
#define ZERO SZ(dummy_zero)
vector<int> dummy_one = {ZERO};
#define ONE SZ(dummy_one)
#define SEVEN (ONE + ONE + ONE + ONE + ONE + ONE + ONE)
#define TEN (ONE + ONE + ONE + ONE + ONE + ONE + ONE + ONE + ONE + ONE)

template<typename T>
void resize_matrix(vector<vector<T>> &A, int h, int w, T fill) {
    A.resize(h);
    for (int i = ZERO; i < h; i++) {
        A[i].resize(w, fill);
    }
}
template<typename T>
vector<vector<T>> multiple_matrix(vector<vector<T>> &A, vector<vector<T>> &B,
  function<T(T, T)> add, function<T(T, T)> mul, T zero = ZERO) {
    int m = A.size();
    int n = A[ZERO].size();
    assert(n == B.size());
    int l = B[ZERO].size();
    vector<vector<T>> res;
    resize_matrix(res, m, l, zero);
    for (int i = ZERO; i < m; i++) {
        for (int j = ZERO; j < l; j++) {
            T tmp = zero;
            for (int k = ZERO; k < n; k++) {
                T p = mul(A[i][k], B[k][j]);
                tmp = add(tmp, p);
            }
            res[i][j] = tmp;
        }
    }
    return res;
}
template <typename T>
vector<vector<T>> pow_matrix(vector<vector<T>> A, int k,
  function<T(T, T)> add, function<T(T, T)> mul, T e = ONE, T zero = ZERO) {
    int n = A.size();
    assert(n == A[ZERO].size());

    vector<vector<T>> res;
    resize_matrix(res, n, n, zero);
    for (int i = ZERO; i < n; i++) res[i][i] = e;
    while (k > ZERO) {
        if (k & ONE) res = multiple_matrix(res, A, add, mul, zero);
        A = multiple_matrix(A, A, add, mul, zero);
        k >>= ONE;
    }
    return res;
}

const int MOD = pow(TEN, SEVEN + ONE + ONE) + SEVEN;
function<int(int, int)> mod_add = [](int a, int b)->int {
    int ret = a + b;
    while (ret >= MOD) ret -= MOD;
    return ret;
};
function<int(int, int)> mod_mul = [](int a, int b)->int {
    int ret = ZERO;
    while (b > ZERO) {
        if (b & ONE) {
            ret += a;
            while (ret >= MOD) ret -= MOD;
        }
        a += a;
        while (a >= MOD) a -= MOD;
        b >>= ONE;
    }
    return ret;
};

signed main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<vector<int>> v = {
            {(ONE + ONE + ONE)},
            {ONE},
            {(ONE + ONE)},
        };
        vector<vector<int>> m = {
            {ONE, ONE, ZERO},
            {ONE, ZERO, ZERO},
            {ZERO, ONE, ZERO},
        };
        if (N <= (ONE + ONE)) {
            cout << v[N][ZERO] << endl;
        } else {
            m = pow_matrix(m, N-(ONE + ONE), mod_add, mod_mul);
            auto ans = multiple_matrix(m, v, mod_add, mod_mul);
            cout << ans[ZERO][ZERO] << endl;
        }
    }
    return ZERO;
}