#include <bits/stdc++.h>
using namespace std;
const int M = 2e6 + 100;
const int N = 1e5 + 100;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n, m, t, k;
vector<int> ans(M);
int main() {
  int T = 1;
  scanf("%d", &T);
  for (int i = 3; i < M; i++)
    ans[i] = (long long)(ans[i - 1] % mod + ans[i - 2] * 2 % mod +
                         4 * (i % 3 == 0)) %
             mod;
  while (T--) {
    scanf("%d", &n);
    printf("%d\n", ans[n]);
  }
  return 0;
}
