#include <bits/stdc++.h>
using namespace std;
int test, n;
long long f[2000001][2];
const int P = 1000000007;
int main() {
  memset(f, 0, sizeof(f));
  f[3][0] = 0;
  f[3][1] = 4;
  for (int i = 4; i <= 2000000; i++)
    f[i][0] = max(f[i - 1][0], f[i - 1][1]) + max(f[i - 2][0], f[i - 2][1]) * 2,
    f[i][0] %= P, f[i][1] = 4 + f[i - 1][0] + 2 * f[i - 2][0], f[i][1] %= P;
  scanf("%d", &test);
  for (; test--;) {
    scanf("%d", &n);
    printf("%lld\n", max(f[n][0], f[n][1]));
  }
}
