#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("sse4.2")
using namespace std;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T, class U>
inline bool chmax(T &x, U y) {
  return x < y ? x = y, 1 : 0;
}
template <class T, class U>
inline bool chmin(T &x, U y) {
  return x > y ? x = y, 1 : 0;
}
template <class T>
inline void sort(T &a) {
  sort((a).begin(), (a).end());
}
template <class T>
inline void rsort(T &a) {
  sort((a).rbegin(), (a).rend());
}
template <class T>
inline void reverse(T &a) {
  reverse((a).begin(), (a).end());
}
template <class T, class U>
inline istream &operator>>(istream &str, pair<T, U> &p) {
  return str >> p.first >> p.second;
}
template <class T>
inline istream &operator>>(istream &str, vector<T> &a) {
  for (auto &i : a) str >> i;
  return str;
}
template <class T>
inline T sorted(T a) {
  sort(a);
  return a;
}
void read() {}
void print() {}
void println() { cout << '\n'; }
template <class T, class... U>
void read(T &x, U &...u) {
  cin >> x;
  read(u...);
}
template <class T, class... U>
void print(const T &x, const U &...u) {
  cout << x;
  print(u...);
}
template <class T, class... U>
void println(const T &x, const U &...u) {
  cout << x;
  println(u...);
}
struct zet {
  int val;
  explicit operator int() const { return val; }
  zet(long long x = 0) {
    val = (x >= -1000000007 && x < 1000000007 ? x : x % 1000000007);
    if (val < 0) val += 1000000007;
  }
  zet(long long a, long long b) {
    *this += a;
    *this /= b;
  }
  zet &operator+=(zet const &b) {
    val += b.val;
    if (val >= 1000000007) val -= 1000000007;
    return *this;
  }
  zet &operator-=(zet const &b) {
    val -= b.val;
    if (val < 0) val += 1000000007;
    return *this;
  }
  zet &operator*=(zet const &b) {
    val = (val * (long long)b.val) % 1000000007;
    return *this;
  }
  friend zet mypow(zet a, long long n) {
    zet res = 1;
    while (n) {
      if (n & 1) res *= a;
      a *= a;
      n >>= 1;
    }
    return res;
  }
  friend zet inv(zet a) { return mypow(a, 1000000007 - 2); }
  zet &operator/=(zet const &b) { return *this *= inv(b); }
  friend zet operator+(zet a, const zet &b) { return a += b; }
  friend zet operator-(zet a, const zet &b) { return a -= b; }
  friend zet operator-(zet a) { return 0 - a; }
  friend zet operator*(zet a, const zet &b) { return a *= b; }
  friend zet operator/(zet a, const zet &b) { return a /= b; }
  friend istream &operator>>(istream &stream, zet &a) {
    return stream >> a.val;
  }
  friend ostream &operator<<(ostream &stream, const zet &a) {
    return stream << a.val;
  }
  friend bool operator==(zet const &a, zet const &b) { return a.val == b.val; }
  friend bool operator!=(zet const &a, zet const &b) { return a.val != b.val; }
  friend bool operator<(zet const &a, zet const &b) { return a.val < b.val; }
};
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(12);
  const int n = 2e6 + 10;
  vector<zet> ans(n);
  for (int i = 2; i < n; i += 6) ans[i] = 4;
  for (int i = 3; i < n; i += 6) ans[i] = -4;
  for (int i = 4; i < n; i += 6) ans[i] = 4;
  for (int i = 1; i < n; ++i) ans[i] += 2 * ans[i - 1];
  int t;
  read(t);
  while (t--) {
    int N;
    read(N);
    println(ans[N - 1]);
  }
  return 0;
}
