#include <stack>
#include <cstdio>
#include <list>
#include <cassert>
#include <set>
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
#pragma comment(linker, "/STACK:102400000,102400000")
#include <string>
#include <map>
#include <cmath>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define LL long long
#define ULL unsigned long long
#define SZ(x) (int)x.size()
#define lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(p, num) memset(p, num, sizeof(p))
#define PB push_back
#define X first
#define Y second
#define ROP freopen("input.txt", "r", stdin);
#define MID(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid+1, r
#define LRT rt << 1
#define RRT rt << 1|1
#define FOR(i, a, b) for (int i=(a); (i) < (b); (i)++)
#define FOOR(i, a, b) for (int i = (a); (i)<=(b); (i)++)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int MAXN = 1e5+10;
const int MOD = 1e9+7;
const int dir[][2] = { {1, 0}, {0, -1}, {-1, 0}, {0, 1} };
const int seed = 131;
int cases = 0;
typedef pair<int, int> pii;
 
struct MATRIX
{
    int row, col;
    LL mat[3][3];
 
    void init(int row, int col, bool one = false)
    {
        this->row = row; this->col = col;
        MS(mat, 0);
        if (!one) return;
        for (int i = 0; i < row; i++) mat[i][i] = 1;
    }
 
    MATRIX operator * (const MATRIX &a)
    {
        MATRIX ret;
        ret.init(row, a.col);
        for (int k = 0; k < col; k++)
            for (int i = 0; i < row; i++) if (mat[i][k])
                for (int j = 0; j < a.col; j++) if (a.mat[k][j])
                    ret.mat[i][j] = (ret.mat[i][j] + mat[i][k] * a.mat[k][j]) % MOD;
        return ret;
    }
 
}ans, M;
 
MATRIX mm[70];
 
inline MATRIX pow_mod(LL n)
{
    MATRIX ret;
    ret.init(3, 3, true);
    int cnt = 0;
    while (n)
    {
        if (n & 1) ret = ret * mm[cnt];
        cnt++;
        n >>= 1;
    }
    return ret;
}
 
void init()
{
    ans.init(1, 3);
    ans.mat[0][0] = 6; ans.mat[0][1] = 6; ans.mat[0][2] = 1;
    M.init(3, 3);
    M.mat[0][0] = 1; M.mat[0][1] = 0; M.mat[0][2] = 0;
    M.mat[1][0] = 6; M.mat[1][1] = 6; M.mat[1][2] = 1;
    M.mat[2][0] = -1; M.mat[2][1] = -1; M.mat[2][2] = 0;
    mm[0] = M;
    for (int i = 1; i < 66; i++) mm[i] = mm[i-1] * mm[i-1];
}
 
void solve(LL n)
{
    ans.init(1, 3);
    ans.mat[0][0] = 6; ans.mat[0][1] = 6; ans.mat[0][2] = 1;
    for (int i = 0; n; i++, n >>= 1) if (n & 1)
        ans = ans * mm[i];
    //ans = ans * pow_mod(n);
    printf("%I64d\n", ((ans.mat[0][0]%MOD) + MOD) %MOD);
}
 
int main()
{
    //ROP;
    int T;
    scanf("%d", &T);
    init();
    while (T--)
    {
        LL n;
        scanf("%lld", &n);
        solve(n-1);
    }
    return 0;
}