#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <utility>
#include <set>
#include <map>

#define reset(a , b) memset(a , b , sizeof(a))
#define REP(i , A) for(int i = 0 ; i < (int)A ; i++)

using namespace std;

const long long MOD = 1000000000000007;
const int MAX = 1000000000;
const int N = 100100;

typedef vector<long long> VI;
typedef vector<VI> matrix;

VI ans , f(4 , 0);
matrix basic(4 , VI(4 , 0));

long long mul(long long A , long long B) {
    if (A <= MAX && B <= MAX) return A * B % MOD;

    if (A < B) swap(A , B);
    long long ret = 2 * mul(A / 2 , B) % MOD;
    if (A & 1) ret = (ret + B) % MOD;
    return ret;
}

matrix operator *(matrix A , matrix B) {
    matrix ans(4 , VI(4 , 0));
    REP(i , 4) REP(j , 4) REP(k , 4)
        ans[i][j] = (ans[i][j] + mul(A[i][k] , B[k][j])) % MOD;
    return ans;
}

VI operator *(VI A , matrix B) {
    VI ans(4 , 0);
    REP(i , 4) REP(j , 4) ans[i] = (ans[i] + mul(A[j] , B[j][i])) % MOD;
    return ans;
}

matrix pw(int n) {
    if (n == 1) return basic;

    matrix tmp = pw(n / 2);
    tmp = tmp * tmp;

    if (n&1) tmp = tmp * basic;

    return tmp;
}

void print(matrix u) {
    REP(i , 4) {
        REP(j , 4) cout << u[i][j];
        cout << endl;
    }
}

int main() {
    //freopen("input.in" , "r" , stdin);
    //freopen("output.out" , "w" , stdout);

    basic[1][0] = 1;
    basic[2][1] = 1;
    basic[0][2] = basic[1][2] = basic[2][2] = 1;
    basic[0][3] = basic[1][3] = basic[2][3] = basic[3][3] = 1;

    f[0] = 1; f[1] = 2; f[2] = 3 , f[3] = 6;

    int T;
    cin >> T;
    while (T--){
        int n;
        cin >> n;

        if (n == 1)
            cout << 1 << endl;
        else if (n == 2) cout << 3 << endl;
        else if (n == 3) cout << 6 << endl;
        else {
            //print(pw(n - 3));
            ans = f * pw(n - 3);
            cout << ans[3] << endl;
        }
    }
}