/*
 _____ _             _              _           _
|_   _| |__   ___   / \   _ __  ___| |__  _   _| |
  | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  | | | | | |  __// ___ \| | | \__ \ | | | |_| | |
  |_| |_| |_|\___/_/   \_\_| |_|___/_| |_|\__,_|_|

*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll,ll>
#define msi         map<string,ll>
#define mis         map<ll, string>
#define rep(i,a,b)    for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) 	for(auto& a : x)
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pair<ll, ll>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define max(a,b)	(a>b?a:b)
#define min(a,b)	(a<b?a:b)

/*	For Debugging	*/
#define DEBUG 		cerr<<"\n>>>I'm Here<<<\n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_iss(x)  cerr << #x << " = " << x << endl;
#define what_is(x)  cerr << #x << " = " << x << " ";

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define DECIMAL(n)  cout << fixed ; cout << setprecision(n);
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define N  100005
#define M 	60

long long pw[M];
vector<vi> mat2D[M];

ll mul(ll p1,ll p2) {
	long long num1 = p1,num2 = p2;
	num1 = (num1 * num2) % hell;;
	return (int) num1;
}

ll add(ll p1, ll p2) {
	if( p1 + p2 >= hell) {
		return p1 + p2 - hell;
	return (p1 + p2);
	}
}

vector<vi> mul(vector<vi> p1, vector<vi> p2) {
	vector<vi> tmp(2,vi(2,0));
	rep(i,0,2) {
		rep(j,0,2) {
			tmp[i][j] = 0;
			rep(k,0,2) {
				tmp[i][j] = add(tmp[i][j], mul(p1[i][k] , p2[k][j]));
			}
		}
	}
	return tmp;
}


vector<vi> expo(vector<vi> base, ll exponent, ll mod) {								//return base^exponent modulo modulus
    vector<vi> ans {{1,0},{0,1}};
    rep(i,0,M) {
    	if(exponent & pw[i]) {
    		ans = mul(ans,mat2D[i]);
    	}
    }
    return ans;
}

ll expo(ll base, ll exponent, ll mod) {								//return base^exponent modulo modulus
    ll ans = 1;
    while(exponent !=0 ) {
        if((exponent&1) == 1) {
            ans = ans*base ;
            ans = ans%mod;
        }
        base = base*base;
        base %= mod;
        exponent>>= 1;
    }
    return ans%mod;
}

void solve()
{
	ll n;
	cin >> n;
	ll num = (n + 1) / 2;
	ll ans;
	if(num == 1) {
		ans = 1;
	} else {
		vector<vi> tmp = {{3,1},{hell - 1,0}};
		what_iss(num);
		tmp = expo(tmp,num, hell);
		ans = tmp[0][0];
	}
	ll num2 = expo(2,n - 1,hell);
	what_is(num2);
	what_iss(ans);
	num2 = expo(num2,hell-2,hell);
	ans = (ans * num2) % hell;
	cout << ans << endl;
	return;
}
int main()
{
	pw[0] = 1;
	rep(i,1, M) {
		pw[i] = pw[i-1] * 2;
	}
	mat2D[0] = {{1,0},{0,1}};
	mat2D[1] = {{3,1},{hell - 1,0}};
	rep(i, 2, M) {
		mat2D[i] = mul(mat2D[i-1],mat2D[i-1]);
	}

	FAST
	int TESTS=1;
	cin>>TESTS;
	rep(i,0,TESTS)
    {
        // cout<<"Case #"<<i+1<<": ";
        solve();
    }
	// TIME
	return 0;
}