#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000010;
const long long mod = 1000000007L;
long long p[maxn][2];
int main() {
  ios::sync_with_stdio(0);
  int t;
  cin >> t;
  p[3][0] = 0;
  p[3][1] = 1;
  for (int i = 4; i < maxn; ++i) {
    p[i][0] = (p[i - 2][1] * 2 % mod + p[i - 1][1]) % mod;
    p[i][1] = (1 + p[i - 2][0] * 2 % mod + p[i - 1][0]) % mod;
    if (i >= 5 && (i - 5) % 3 == 0) p[i][1] = p[i][0];
  }
  for (int T = 0; T < t; ++T) {
    int n;
    cin >> n;
    long long ans = p[n][1] * 4 % mod;
    printf("%lld\n", ans);
  }
}
