#include <bits/stdc++.h>
using namespace std;
int main() {
  int MAXN = 1e6 + 1e6 + 1;
  long long p = 1e9 + 7;
  vector<long long> v1(MAXN), s1(MAXN), a1(MAXN);
  vector<long long> v0(MAXN), s0(MAXN), a0(MAXN), f(MAXN);
  v1[1] = 1;
  f[1] = 1;
  for (int i = 2; i < MAXN; ++i) {
    v1[i] = (v0[i - 1] + 2 * s0[i - 1]) % p;
    s1[i] = v1[i - 1];
    a1[i] = (a1[i - 1] + s1[i - 1]) % p;
    v0[i] = (v1[i - 1] + 2 * s1[i - 1]) % p;
    s0[i] = v0[i - 1];
    a0[i] = (a0[i - 1] + s0[i - 1]) % p;
    if (i >= 3) {
      f[i] = (f[i - 3] + v0[i] + v1[i]) % p;
    } else {
      f[i] = 1;
    }
  }
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    int n;
    cin >> n;
    if (n < 3) {
      cout << 0 << endl;
    } else {
      n = n - 2;
      cout << (f[n] * 4) % p << endl;
    }
  }
  return 0;
}
