#include <bits/stdc++.h>
using namespace std;
long long dp[2000001][2];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tc;
  cin >> tc;
  for (int i = 3; i <= 2000000; i++) {
    dp[i][0] = ((2 * max(dp[i - 2][0], dp[i - 2][1])) % 1000000007 +
                max(dp[i - 1][0], dp[i - 1][1])) %
               1000000007;
    dp[i][1] =
        (((2 * dp[i - 2][0]) % 1000000007 + dp[i - 1][0]) % 1000000007 + 1) %
        1000000007;
  }
  while (tc--) {
    int n;
    cin >> n;
    cout << (max(dp[n][0], dp[n][1]) * 4) % 1000000007 << endl;
  }
}
