#include <bits/stdc++.h>
using namespace std;
long long countbit(long long a) {
  long long c = 0;
  while (a) {
    if (a & 1) c++;
    a >>= 1;
  }
  return (c);
}
long long power(long long a, long long p, long long m = 1000000007) {
  a %= m;
  long long val = 1;
  while (p > 0) {
    if (p & 1) {
      val = (val * a) % m;
    }
    a = (a * a) % m;
    p >>= 1;
  }
  return (val);
}
int count(unsigned long long a) {
  int k = 0;
  if (a == 0) return 0;
  while (a) {
    a >>= 1;
    k++;
  }
  return k - 1;
}
bool comp1(pair<int, int>& a, pair<int, int>& b) {
  if (a.first == b.first) return a.second < b.second;
  return a.first > b.first;
}
bool comp2(pair<int, int>& a, pair<int, int>& b) {
  if (a.second == b.second) return a.first > b.first;
  return a.second < b.second;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long n, i, j;
  std::vector<long long> sol(2000001);
  sol[0] = sol[1] = sol[2] = 0;
  sol[3] = 1;
  long long fs = 3, fs2;
  long long ss = 1, ss2;
  for (i = 4; i <= 2000000; ++i) {
    sol[i] = (sol[i - 3] + ss) % 1000000007;
    fs2 = 2 * ss + fs;
    ss2 = fs;
    fs = fs2 % 1000000007;
    ss = ss2 % 1000000007;
  }
  long long T = 1;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    if (n < 3) {
      cout << "0\n";
    } else {
      long long p = sol[n];
      p = (p + p) % 1000000007;
      p = (p + p) % 1000000007;
      cout << p << "\n";
    }
  }
}
