#include <bits/stdc++.h>
using namespace std;
const long long N = 2e6 + 2, MOD = 1e9 + 7;
inline long long add(long long a, long long b) {
  return ((a % MOD) + (b % MOD)) % MOD;
}
inline long long mul(long long a, long long b) {
  return ((a % MOD) * (b % MOD)) % MOD;
}
inline long long sub(long long a, long long b) {
  return ((a % MOD) - (b % MOD) + MOD) % MOD;
}
long long lf[N], total[N], finalAns[N];
long long mod(long long a, long long b) {
  a = (a > 0) ? a : (-a / b + 1) * b + a;
  return a % b;
}
void solve() {
  long long n;
  cin >> n;
  cout << finalAns[n] << "\n";
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  lf[2] = 1;
  lf[1] = 1;
  for (long long i = 3; i < 2e6 + 2; i++) {
    lf[i] = add(lf[i - 1], lf[i - 2] * 2);
  }
  total[2] = 1;
  total[3] = 3;
  total[1] = 1;
  finalAns[1] = 0;
  finalAns[2] = 0;
  for (long long i = 4; i < N; i++) total[i] = add(lf[i], total[i - 3]);
  for (long long i = 3; i < N; i++) finalAns[i] = mul(total[i - 2], 4);
  long long t;
  cin >> t;
  for (long long tt = 1; tt < t + 1; tt++) {
    solve();
  }
  return 0;
}
