#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long POW(long long x, long long y) {
  long long ans = 1;
  long long base = x;
  while (y) {
    if (y & 1) {
      ans *= base;
    }
    base = base * base;
    y = y >> 1;
  }
  return ans;
}
const long long M = 2e6 + 1;
long long a[M], b[M], c[M], gen[M], ans[M], leaf[M], dp[M];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long n, i, j, k, t, temp, tc;
  a[1] = 1;
  b[1] = 0;
  c[1] = 0;
  a[0] = 0;
  b[0] = 0;
  c[0] = 0;
  gen[1] = 1;
  gen[0] = 1;
  ans[0] = 0;
  ans[1] = 0;
  ans[2] = 0;
  leaf[0] = 0;
  dp[0] = 0;
  dp[1] = 0;
  dp[2] = 0;
  dp[3] = 2;
  for (i = 2; i <= M - 1; i++) {
    a[i] = (a[i - 1] + 2 * b[i - 1]) % MOD;
    b[i] = a[i - 1];
    c[i] = b[i - 1];
    gen[i] = ((a[i] - c[i]) + 100 * MOD) % MOD;
    leaf[i] = (2 * c[i]) % MOD;
  }
  for (i = 4; i <= M - 1; i++) {
    dp[i] = (leaf[i] + dp[i - 3]) % MOD;
  }
  cin >> tc;
  while (tc--) {
    cin >> n;
    long long final = (2 * dp[n]) % MOD;
    cout << final << endl;
  }
  return 0;
}
