//  Copyright 2020 Nikita Golikov

#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;
using ui64 = uint64_t;

#ifdef GOLIKOV
mt19937_64 rng(566);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif

template <typename T>
T rnd_helper(T from, T to, true_type) {
  return uniform_int_distribution<T>(from, to)(rng);
}

template <typename T>
T rnd_helper(T from, T to, false_type) {
  return uniform_real_distribution<T>(from, to)(rng);
}

template <typename T>
T rnd(T from, T to) {
  return rnd_helper(from, to, is_integral<T>{});
}

template <typename A, typename B, typename Cmp>
bool set_min(A &x, B const &y, Cmp &&cmp) {
  if (cmp(y, x)) {
    x = y;
    return true;
  }
  return false;
}

template <typename A, typename B>
bool set_min(A &x, B const &y) {
  return set_min(x, y, less<typename common_type<A, B>::type>{});
}

template <typename A, typename B>
bool set_max(A &x, B const &y) {
  return set_min(x, y, greater<typename common_type<A, B>::type>{});
}

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename K, typename V>
using ordered_map = tree<K, V, less<K>, rb_tree_tag,
                         tree_order_statistics_node_update>;

//  https://codeforces.com/blog/entry/62393
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t
        FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return static_cast<size_t>(splitmix64(x + FIXED_RANDOM));
  }
};

#ifdef __cpp_deduction_guides
template <typename F>
struct rec_fun {
  F fun;

  rec_fun(F &&fun_) : fun(std::forward<F>(fun_)) {}

  template <typename... Args>
  decltype(auto) operator()(Args &&... args) const {
    return fun(*this, std::forward<Args>(args)...);
  }
};
#endif

#ifdef __cpp_inline_variables
template <typename T>
inline constexpr auto type_min = numeric_limits<T>::lowest();

template <typename T>
inline constexpr auto type_max = numeric_limits<T>::max();
#endif

//  fast alloc
#if 0
int const MAX_MEM = 1e8;
int mpos = 0;
char mem[MAX_MEM];
void* operator new(size_t n) {
  mpos += n;
  return (void*)(mem + mpos - n);
}
void operator delete (void*) noexcept {}
#endif

//  pragmas
#if 0
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("unroll-loops")
#endif

template <int MOD>
struct modular {
  int val{};

  static int norm(i64 x) {
    int res = -MOD <= x && x < MOD ? x : (int) (x % MOD);
    if (res < 0) {
      res += MOD;
    }
    return res;
  }

  modular() = default;
  modular(int x, bool do_norm = false) : val(do_norm ? norm(x) : x) {}
  modular(i64 x) : val(norm(x)) {}

  int to_int() const {
    return val;
  }
  modular& operator+=(modular other) {
    val += other.val;
    if (val >= MOD) {
      val -= MOD;
    }
    return *this;
  }
  friend modular operator+(modular x, modular y) {
    return x += y;
  }
  modular& operator-=(modular other) {
    val -= other.val;
    if (val < 0) {
      val += MOD;
    }
    return *this;
  }
  friend modular operator-(modular x, modular y) {
    return x -= y;
  }
  modular& operator++() {
    if (++val == MOD) {
      val = 0;
    }
    return *this;
  }
  modular& operator--() {
    if (--val < 0) {
      val = MOD - 1;
    }
    return *this;
  }
  friend modular operator*(modular x, modular y) {
    return modular{(i64) x.val * y.val};
  }
  modular operator*=(modular other) {
    return *this = *this * other;
  }
  friend bool operator==(modular x, modular y) {
    return x.to_int() == y.to_int();
  }
  friend bool operator!=(modular x, modular y) {
    return x.to_int() != y.to_int();
  }
  modular operator-() const {
    return 0 - *this;
  }
  friend istream& operator>>(istream& in, modular& x) {
    return in >> x.val;
  }
  friend ostream& operator<<(ostream& out, modular x) {
    return out << x.val;
  }
  explicit operator bool() const {
    return bool(val);
  }
};

template <int MOD>
modular<MOD> power(modular<MOD> x, i64 deg) {
  if (!x) {
    return !deg;
  }
  deg %= MOD - 1;
  if (deg < 0) {
    deg += MOD - 1;
  }
  modular<MOD> res = 1;
  while (deg) {
    if (deg & 1) {
      res *= x;
    }
    x *= x;
    deg /= 2;
  }
  return res;
}

template <int MOD>
modular<MOD> inv(modular<MOD> x) {
  return power(x, -1);
}

template <int MOD>
modular<MOD> operator/(modular<MOD> x, modular<MOD> y) {
  return x * inv(y);
}

template <int MOD>
modular<MOD>& operator/=(modular<MOD>& x, modular<MOD> other) {
  return x = x / other;
}

int const MOD = (int) 1e9 + 7;
using mint = modular<MOD>;

template <typename T>
vector<T> berlekamp(vector<T> const& a) {
  vector<T> b{1};
  vector<T> c{1};
  T prev_d = 1;
  int len = 0;
  int deg = 1;
  for (int n = 1; n <= (int) a.size(); ++n, ++deg) {
    T d = 0;
    for (int i = 0; i <= len; ++i) {
      d += a[n - i - 1] * c[i];
    }
    if (!d) continue;
    auto new_c = c;
    auto coef = d / prev_d;
    new_c.resize(max(c.size(), b.size() + deg));
    for (int i = 0; i < (int) b.size(); ++i) {
      new_c[i + deg] -= coef * b[i];
    }
    if (n - len <= len) {
      c = move(new_c);
      continue;
    }
    len = n - len;
    b = move(c);
    c = move(new_c);
    prev_d = d;
    deg = 0;
  }
  vector<T> ans(c.begin() + 1, c.begin() + 1 + len);
  for (auto& x : ans) x = -x;
  return ans;
}

//  init satisfies c
template <typename T>
T nth_linear(vector<T> const& init, vector<T> const& c, i64 n) {
  int k = (int) c.size();
  int m = (int) init.size();
  if (!k || !m) return 0;
  vector<T> p(k), q(k + 1);
  auto multiply = [](auto const& a, auto const& b) {
    int need = max(0, (int) (a.size() + b.size()) - 1);
    vector<T> ans(need);
    for (int i = 0; i < (int) a.size(); ++i) {
      for (int j = 0; j < (int) b.size(); ++j) {
        ans[i + j] += a[i] * b[j];
      }
    }
    return ans;
  };
  auto prod = multiply(init, c);
  p[0] = init[0];
  for (int i = 1; i < min(k, m); ++i) {
    p[i] = init[i] - prod[i - 1];
  }
  q[0] = 1;
  for (int i = 0; i < k; ++i) q[i + 1] = -c[i];
  auto select_terms = [](auto const& vec, int par) {
    vector<T> res;
    res.reserve((vec.size() + 1) / 2);
    for (int i = par; i < (int) vec.size(); i += 2) {
      res.push_back(vec[i]);
    }
    return res;
  };
  while (n) {
    auto q_neg = q;
    for (int i = 1; i < (int) q.size(); i += 2) {
      q_neg[i] = -q_neg[i];
    }
    auto new_q = multiply(q, q_neg);
    auto new_p = multiply(p, q_neg);
    p = select_terms(new_p, n % 2);
    q = select_terms(new_q, 0);
    n /= 2;
  }
  return p.empty() ? 0 : p[0];
}

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int const N = 50;
  int const D = 5;

  vector<vector<mint>> dp(D + 1, vector<mint>(N));
  dp[0][0] = 1;
  for (int d = 1; d <= D; ++d) {
    for (int n = 0; n < N; ++n) {
      for (int a = 0; a < n; ++a) {
        for (int b = a + 1; b < n && a + b <= n; ++b) {
          dp[d][n] += dp[d - 1][n - a - b] * (b - a);
        }
      }
    }
  }
  auto vals = dp.back();
  for (int i = 0; i + 1 < (int) vals.size(); ++i) vals[i + 1] += vals[i];
  auto rec = berlekamp(vals);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    cout << nth_linear(vals, rec, n + 2) << '\n';
  }

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}


Measured memory_bytes: 3656