#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll MOD=mod;
ll sum(ll A, ll B)
{
        A = (A + MOD) % MOD;
        B = (B + MOD) % MOD;
        ll ans = (A + B) % MOD;
        ans = (ans + MOD) % MOD;
        return ans;
}
ll f(ll a, ll n)
{
        ll res = a, ans = 0;
        while (n)
        {
                if (n % 2)
                        ans = (ans + res) % MOD;
                res = (res + res) % MOD;
                n /= 2;
        }
        return ans;
}
struct matran
{
        ll a[4][4];
        void print()
        {
                for (ll i = 0; i < 4; i++)
                {
                        for (ll j = 0; j < 4; j++)
                                cout << a[i][j] << " ";
                        cout << '\n';
                }
        }
};
matran mot, M;
struct matran_1
{
        ll a[1][4];
        void print()
        {
                for (ll i = 0; i < 1; i++)
                {
                        for (ll j = 0; j < 4; j++)
                                cout << a[i][j] << " ";
                        cout << '\n';
                }
        }
};
matran prod(matran A, matran B)
{
        matran C;
        for (ll i = 0; i < 4; i++)
                for (ll j = 0; j < 4; j++)
                        C.a[i][j] = 0;
        for (ll i = 0; i < 4; i++)
        {
                for (ll j = 0; j < 4; j++)
                {
                        for (ll k = 0; k < 4; k++)
                                C.a[i][j] = sum(C.a[i][j], f(A.a[i][k], B.a[k][j]));
                }
        }
        return C;
}
matran_1 prod1(matran_1 A, matran B)
{
        matran_1 C;
        for (ll i = 0; i < 1; i++)
                for (ll j = 0; j < 4; j++)
                        C.a[i][j] = 0;
        for (ll i = 0; i < 1; i++)
                for (ll j = 0; j < 4; j++)
                        for (ll k = 0; k < 4; k++)
                                C.a[i][j] = sum(C.a[i][j], f(A.a[i][k], B.a[k][j]));
        return C;
}
matran po(matran A, ll n)
{
        matran res = A, ans = mot;
        while(n){
                if(n%2) ans = prod(ans,res);
                res = prod(res,res);
                n/=2;
        }
        return ans;
}
int main()
{
	
        ll unit[4][4] = {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
        ll MM[4][4] = {{4, 0, 0, 0}, {1, 3, 1, 0}, {0, 2, 0, 0}, {2, 0, 0, 1}};
        
        for (ll i = 0; i < 4; i++)
        {
                for (ll j = 0; j < 4; j++)
                {
                        mot.a[i][j] = unit[i][j];
                        M.a[i][j] = MM[i][j];
                }
        }
        ll tmp[1][4] = {{1, 1, 1, 1}};
        matran_1 initi;
        for (ll i = 0; i < 1; i++)
        {
                for (ll j = 0; j < 4; j++)
                        initi.a[i][j] = tmp[i][j];
        }
        ll testcase;
        cin>>testcase;
        while(testcase--){
                ll nn;
                cin>>nn;
                matran_1 lala = prod1(initi,po(M,nn));
                cout<<lala.a[0][0]<<'\n';
        }
        return 0;
}