#include <bits/stdc++.h>
using namespace std;
long long int a[2000001], b[2000001], c[2000001], d[2000001], dp[2000001];
long long int gcdExtended(long long int a, long long int b, long long int *x,
                          long long int *y);
long long int modInverse(long long int b, long long int m) {
  long long int x, y;
  long long int g = gcdExtended(b, m, &x, &y);
  if (g != 1) return -1;
  return (x % m + m) % m;
}
long long int modDivide(long long int a, long long int b, long long int m) {
  a = a % m;
  long long int inv = modInverse(b, m);
  return (inv * a) % m;
}
long long int gcdExtended(long long int a, long long int b, long long int *x,
                          long long int *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t, i, mod = 1000000007;
  cin >> t;
  a[1] = 0;
  b[1] = 0;
  c[1] = 1;
  d[1] = 0;
  a[2] = 0;
  b[2] = 1;
  c[2] = 1;
  d[2] = 0;
  dp[1] = 0;
  dp[2] = 0;
  dp[3] = 1;
  dp[4] = 1;
  dp[5] = 3;
  for (i = 3; i <= 2000000; i++) {
    a[i] = a[i - 1] + b[i - 1];
    b[i] = c[i - 1];
    c[i] = c[i - 1] + c[i - 2] + c[i - 2];
    d[i] = (a[i] + 1) / 2;
    a[i] = a[i] % mod;
    b[i] = b[i] % mod;
    c[i] = c[i] % mod;
    d[i] = d[i] % mod;
  }
  for (i = 6; i <= 2000000; i++) {
    dp[i] = dp[i - 3] + d[i];
    dp[i] = dp[i] % mod;
  }
  while (t--) {
    long long int n;
    cin >> n;
    cout << (dp[n] * 4) % mod << endl;
  }
  return 0;
}
