#include <bits/stdc++.h>
using namespace std;
const long long int mod = (long long int)1e9 + 7;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  const long long int mxn = 2e6;
  vector<long long int> NC(mxn + 10, 0), OC(mxn + 10, 0), TC(mxn + 10, 0);
  vector<long long int> dp(mxn + 10, 0);
  NC[1] = 1;
  NC[2] = 1, OC[2] = 1;
  for (long long int i = 3; i <= mxn; i++) {
    OC[i] = NC[i - 1];
    NC[i] = NC[i - 1] + 2 * OC[i - 1] % mod;
    TC[i] = OC[i - 1];
    dp[i] = dp[i - 3] + 4 * TC[i];
    dp[i] %= mod;
  }
  long long int TESTS = 1;
  cin >> TESTS;
  for (long long int TEST = 1; TEST <= TESTS; TEST++) {
    long long int n;
    cin >> n;
    cout << dp[n] << "\n";
  }
  return 0;
}
