#include <bits/stdc++.h>
using namespace std;
int N;
long long dp[2000005][2];
void pre() {
  memset(dp, -1, sizeof(dp));
  for (int i = 1; i <= 2; i++) dp[i][0] = dp[i][1] = 0;
  dp[3][0] = 1;
  dp[3][1] = 0;
  dp[4][0] = 1, dp[4][1] = 1;
  for (int i = 5; i <= 2000000; i++) {
    dp[i][1] = 2 * dp[i - 2][0] + dp[i - 1][0];
    dp[i][0] = max(dp[i][1], 1 + 2 * dp[i - 2][1] + dp[i - 1][1]);
    dp[i][1] %= 1000000007;
    dp[i][0] %= 1000000007;
  }
}
int main() {
  pre();
  int T;
  cin >> T;
  while (T--) {
    int x;
    cin >> x;
    cout << dp[x][0] * 4 % 1000000007 << endl;
  }
  return 0;
}
