#include<bits/stdc++.h>

using namespace std;

uint64_t mod = 1000000007;

void fastIOI()
{   
    freopen("penguin.in", "r", stdin);
    freopen("penguin.out", "w", stdout);
    ios_base :: sync_with_stdio(0);
    cout.tie(nullptr);
    cin.tie(nullptr);
}

void multiply (int64_t A[4][4], int64_t B[4][4])
{
    int64_t R[4][4];
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            R[i][j] = 0;
            for (int k = 0; k < 4; k++)
            {
                R[i][j] = (R[i][j] + A[i][k] * B[k][j]);
                if (R[i][j]<0){
                    R[i][j] = R[i][j] % -mod;
                }
                else{
                    R[i][j] = R[i][j] % mod;
                }
            }
        }
    }
    
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            A[i][j] = R[i][j];
            //cout<<R[i][j]<<" ";
        }
        //cout<<endl;
    }
}

// Raise matrix A to the power of n in O(log n).
void power_matrix (int64_t A[4][4], uint64_t n)
{
    int64_t B[4][4];
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            B[i][j] = A[i][j];
        }
    }
    
    // A = A * A ^ (n - 1).
    n = n - 1;
    while (n > 0)
    {
        // If n is odd, A = A * B.
        if (n & 1)
            multiply (A, B);
            
        // B = B * B.
        multiply (B,B);
        
        // n = n / 2.
        n = n >> 1;  
    }
}

int64_t solve_recurrence (int64_t A[4][4], int64_t B[4][1], uint64_t n){
    //Base Cases.
    if (n < 4)
        return B[4 - 1 - n][0];
    
    // A = A ^ (n - N + 1).
    power_matrix (A, n - 4 + 1);
    
    int64_t result = 0;
    
    for (int i = 0; i < 4; i++)
        result = (result + A[0][i] * B[i][0]) % mod;
    
    return result;
}

int solve2(uint64_t n){
    int64_t A[4][4] = {{0,2,1,-1},{1,0,0,0},{0,1,0,0},{0,0,1,0}};
    int64_t B[4][1] = {{3}, {1}, {1}, {1}};
    return solve_recurrence (A, B, n);
}
int main(){
	fastIOI();
	int t;
	cin>>t;
	vector<uint64_t> ns(t);
	uint64_t maxn = 0;
	for(int i=0;i<t;i++) cin>>ns[i];
	for(int i=0;i<t;i++) {
	    cout<<solve2(ns[i])<<'\n';
	}
	return 0;
}