#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int inf = 0x7fffffff;
const ll INF = 0x7fffffffffffffff;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
ll z[2000006];
ll x[2000006];
ll mod0[2000006];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a, b, c, d, e, f, g, T;
  z[0] = 0;
  z[1] = 0;
  z[2] = 1;
  z[3] = 1;
  for (int i = 4; i <= 2000000; i++) {
    z[i] = z[i - 2] * 3 + z[i - 3] * 2;
    z[i] %= mod;
  }
  mod0[2] = 1;
  for (int i = 3; i <= 2000000; i++) {
    mod0[i] = mod0[i - 3] + z[i];
    mod0[i] %= mod;
  }
  cin >> T;
  while (T--) {
    cin >> a;
    cout << mod0[a - 1] * 4 % mod << endl;
  }
}
