#include <bits/stdc++.h>
using namespace std;
#define MAXN 4
const int MOD = 1e9+7;

int T, n;
long long K[MAXN][MAXN], C[MAXN][MAXN], E[MAXN][MAXN];

void mul(long long A[MAXN][MAXN], long long B[MAXN][MAXN]){
	memset(C, 0, sizeof(C));
	
	for (int i=1; i<MAXN; i++){
		for (int j=1; j<MAXN; j++){
			for (int k=1; k<MAXN; k++) C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD;
		}
	}
	
	memcpy(A, C, sizeof(C));
}

void qpow(long long A[MAXN][MAXN], int k){
	for (int i=1; i<MAXN; i++) E[i][i] = 1;
	while (k){
		if (k & 1) mul(E, A);
		mul(A, A);
		k >>= 1;
	}
	memcpy(A, E, sizeof(E));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> T;
	
	while (T--){
		cin >> n;
		if (n <= 3){
			cout << "1\n";
			continue;
		}
		
		memset(K, 0, sizeof(K));
		K[1][1] = K[1][3] = K[2][1] = K[3][2] = 1;
		
		qpow(K, n);
		
		cout << K[2][1] << '\n';
	}
	
	return 0;
}

真没找出来有什么错误，但是样例就是过不了……