#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)
int add(int a, int b) {
    while (b != ZERO) {
        int c = (a & b) << ONE;
        a ^= b;
        b = c;
    }
    return a;
}
void increment(int &x) {
    x = add(x, ONE);
}
int neg(int x) {
    return add((~x), ONE);
}

#define SEVEN (add(add(add(add(add(add(ONE, ONE), ONE), ONE), ONE), ONE), ONE))
#define TEN (add(add(add(add(add(add(add(add(add(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; increment(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; increment(i)) {
        for (int j = ZERO; j < l; increment(j)) {
            T tmp = zero;
            for (int k = ZERO; k < n; increment(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; increment(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 = add(pow(TEN, add(SEVEN, add(ONE, ONE))), SEVEN);
function<int(int, int)> mod_add = [](int a, int b) {
    int ret = add(a, b);
    while (ret >= MOD) ret = add(ret, neg(MOD));
    return ret;
};
function<int(int, int)> mod_mul = [](int a, int b) {
    int ret = ZERO;
    while (b > ZERO) {
        if (b & ONE) {
            ret = add(ret, a);
            while (ret >= MOD) ret = add(ret, neg(MOD));
        }
        a = add(a, a);
        while (a >= MOD) a = add(a, neg(MOD));
        b >>= ONE;
    }
    return ret;
};

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