#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const long long infll = 0x7fffffffffffffff;
const int mod = (int)(1e9) + 7;
const int inf = 0x7fffffff;
const int maxn = (int)(2e6) + 7;
const int maxm = 300;
int _;
long long n, f[maxn];
int main() {
  for (int i = 3; i <= (long long)(2e6); i++) {
    f[i] = (f[i - 1] + f[i - 2] * 2 % mod + (i % 3 ? 0 : 1)) % mod;
  }
  for (scanf("%d", &_); _; _--) {
    scanf("%lld", &n);
    printf("%lld\n", f[n] * 4 % mod);
  }
  return 0;
}
