#include <bits/stdc++.h>
using namespace std;
int moder = (int)1e9 + 7;
int child[2000005][3];
int max_val[2000005];
void prepare() {
  int limit = (int)2e6;
  child[1][0] = 1;
  for (int i = 2; i <= limit; i++) {
    child[i][0] =
        ((long long)child[i - 1][0] + (long long)2 * child[i - 1][1]) % moder;
    child[i][1] = child[i - 1][0];
  }
  for (int i = 3; i <= limit; i++)
    max_val[i] =
        ((long long)max_val[i - 3] + (long long)child[i - 1][1] * 4) % moder;
}
void solve() {
  int num;
  scanf("%d", &num);
  printf("%d\n", max_val[num]);
}
int main() {
  prepare();
  int tester;
  scanf("%d", &tester);
  while (tester--) solve();
}
