#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9 + 7;
const long long int N = 2e6 + 10;
long long int a[N];
void solve() {
  long long int n;
  cin >> n;
  cout << a[n] << "\n";
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  a[1] = a[2] = 0;
  a[3] = 4;
  for (long long int i = 4; i <= 2e6; i++) {
    a[i] = (a[i - 1] + 2 * a[i - 2]) % mod;
    if (i % 3 == 0) {
      a[i] += 4 * 1LL;
      a[i] %= mod;
    }
  }
  long long int t;
  cin >> t;
  while (t--) {
    solve();
  }
}
