TILE

#include <iostream>
#include <cstdio>
#include <cstring>
#define task "TILE"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2 + 2;
const ll mod = 1e9 + 7;
struct Matrix{
    ll a[N][N];
    Matrix() {memset(a, 0, sizeof a);}
    Matrix operator * (const Matrix &m) {
        Matrix ans;
        for(int i = 1; i < 3; ++i)
            for(int j = 1; j < 3; ++j)
                for(int t = 1; t < 3; ++t)
                    ans.a[i][j] = (ans.a[i][j] + a[i][t] * m.a[t][j] % mod) % mod;
        return ans;
    }
};
ll n;

void Read(){
    cin >> n;
}

Matrix Pow(Matrix a, ll b){
    Matrix tmp;
    for(int i = 1; i < 3; ++i)
        tmp.a[i][i] = 1;
    for(; b > 0; b >>= 1){
        if(b & 1) tmp = tmp * a;
        a = a * a;
    }
    return tmp;
}

void Solve(){
    Matrix ans, cur;
    cur.a[1][2] = cur.a[2][2] = 1;
    cur.a[2][1] = 2;
    ans.a[1][1] = 1;
    ans.a[2][1] = 3;
    if(n == 1){
        cout << 1 << "\n";
        return;
    }
    cur = Pow(cur, n - 1ll);
    cur = cur * ans;
    cout << cur.a[1][1] << "\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); if(fopen(task".INP", "r"))
    freopen(task".INP", "r", stdin),
    freopen(task".OUT", "w", stdout);
    int t;
    cin >> t;
    while(t--)
        Read(),
        Solve();
}