#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int mod = 1e9 + 7;
struct mat {
	int a[5][5];
	mat () {memset (a, 0, sizeof(a));}
	mat operator * (const mat &B) const {
		mat C;
		for (int i = 1; i <= 3; i ++) {
			for (int j = 1; j <= 3; j ++) {
				for (int k = 1; k <= 3; k ++) {
					C.a[i][j] = (C.a[i][j] + a[i][k] * B.a[k][j]) % mod;
					C.a[i][j] %= mod;
				}
			}
		}
		return C;
	}
}ans, base;
void init () {
	memset (base.a, 0, sizeof (base.a));
	memset (ans.a, 0, sizeof (ans.a));
	base.a[2][1] = base.a[1][3] = base.a[3][2] = base.a[3][3] = 1;
	ans.a[1][1] = ans.a[1][2] = ans.a[1][3] = 1;
}
int qpow (int b) {
	while (b) {
		if (b & 1) ans = ans * base;
		base = base * base;
		b >>= 1; 
	}
}
signed main () {
	ios :: sync_with_stdio (false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		if (n <= 3) {
			cout << 1 << endl;
			continue;
		} 
		init ();
		qpow (n - 3);
		cout << (ans.a[1][3] + ans.a[2][3] + ans.a[3][3]) % mod << endl;
	}
} 
/*
a[i-3] a[i-2] a[i-1] 
0 0 1
1 0 0
0 1 1
a[i-2] a[i-1] a[i] 
*/

RT，样例都过了