#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 8;
const double pi = 3.14159265359;
template <class T>
T fac(T n) {
  T res = 1, i;
  for (i = 2; i <= n; i++) res *= i;
  return res;
}
template <class T>
T lcm(T a, T b) {
  return (a * b) / __gcd(a, b);
}
template <class T>
T digitsum(T x) {
  T sum = 0;
  while (x) {
    sum += x % 10;
    x /= 10;
  }
  return sum;
}
void nPermute(string str, long long n) {
  sort((str).begin(), (str).end());
  long long i = 1;
  do {
    if (i == n) break;
    i++;
  } while (next_permutation(str.begin(), str.end()));
  cout << str << endl;
}
vector<long long> factors(long long n) {
  vector<long long> f;
  for (long long x = 2; x * x <= n; x++) {
    while (n % x == 0) {
      f.push_back(x);
      n /= x;
    }
  }
  if (n > 1) f.push_back(n);
  return f;
}
bool prime(long long n) {
  if (n < 2) return false;
  for (long long x = 2; x * x <= n; x++)
    if (n % x == 0) return false;
  return true;
}
long long ncr(long long n, long long k) {
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; i++) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
tuple<long long, long long, long long> Gcd(long long a, long long b) {
  if (b == 0)
    return {1, 0, a};
  else {
    long long x, y, g;
    tie(x, y, g) = Gcd(b, a % b);
    return {y, x - (a / b) * y, g};
  }
}
template <class T>
T binpow(T a, T b, T m) {
  a %= m;
  T res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
const long long N = 2e6 + 5;
long long a[N];
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  for (long long i = 3; i < N; i++)
    a[i] = (a[i - 1] + 2 * a[i - 2] + (i % 3 == 0)) % MOD;
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    cout << (4 * a[n]) % MOD << endl;
  }
  cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
}
