// Author: Tyler Wang

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <string_view>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

using namespace std;

template <class C>
constexpr auto ssize(const C& c)
    -> std::common_type_t<std::ptrdiff_t,
                          std::make_signed_t<decltype(c.size())>> {
  using R = std::common_type_t<std::ptrdiff_t,
                               std::make_signed_t<decltype(c.size())>>;
  return (R)c.size();
}

template <class T, std::ptrdiff_t N>
constexpr std::ptrdiff_t ssize(const T (&)[N]) noexcept {
  return N;
}

template <typename T>
constexpr std::enable_if_t<std::is_unsigned_v<T>, bool> has_single_bit(
    T x) noexcept {
  return x != 0 && (x & (x - 1)) == 0;
}

template <typename T>
constexpr std::enable_if_t<std::is_unsigned_v<T>, int> countl_zero(
    T x) noexcept {
  if constexpr (sizeof(T) <= sizeof(unsigned)) {
    return __builtin_clz(x) - (std::numeric_limits<unsigned>::digits -
                               std::numeric_limits<T>::digits);
  } else if constexpr (sizeof(T) <= sizeof(unsigned long)) {
    return __builtin_clzl(x) - (std::numeric_limits<unsigned long>::digits -
                                std::numeric_limits<T>::digits);
  } else {
    static_assert(sizeof(T) <= sizeof(unsigned long long));
    return __builtin_clzll(x) -
           (std::numeric_limits<unsigned long long>::digits -
            std::numeric_limits<T>::digits);
  }
}

template <typename T>
constexpr std::enable_if_t<std::is_unsigned_v<T>, int> countr_zero(
    T x) noexcept {
  if constexpr (sizeof(T) <= sizeof(unsigned)) {
    return __builtin_ctz(x);
  } else if constexpr (sizeof(T) <= sizeof(unsigned long)) {
    return __builtin_ctzl(x);
  } else {
    static_assert(sizeof(T) <= sizeof(unsigned long long));
    return __builtin_ctzll(x);
  }
}

template <typename T>
constexpr std::enable_if_t<std::is_unsigned_v<T>, int> popcount(T x) noexcept {
  if constexpr (sizeof(T) <= sizeof(unsigned)) {
    return __builtin_popcount(x);
  } else if constexpr (sizeof(T) <= sizeof(unsigned long long)) {
    return __builtin_popcountl(x);
  } else {
    static_assert(sizeof(T) <= sizeof(unsigned long long));
    return __builtin_popcountll(x);
  }
}

template <typename T>
constexpr std::enable_if_t<std::is_unsigned_v<T>, T> bit_width(T x) noexcept {
  return (T)(std::numeric_limits<T>::digits - countl_zero(x));
}

template <typename T>
constexpr std::enable_if_t<std::is_unsigned_v<T>, T> bit_ceil(T x) noexcept {
  return (T)(x <= 1 ? 1 : (T)1 << bit_width((T)(x - 1)));
}

template <typename T>
constexpr std::enable_if_t<std::is_unsigned_v<T>, T> bit_floor(T x) noexcept {
  return (T)(x == 0 ? 0 : (T)1 << (bit_width(x) - 1));
}

#if defined(__GNUC__) && !defined(__clang__)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

template <typename Key, typename Compare = std::less<Key>,
          typename Allocator = std::allocator<Key>>
using ordered_set =
    __gnu_pbds::tree<Key, __gnu_pbds::null_type, Compare,
                     __gnu_pbds::rb_tree_tag,
                     __gnu_pbds::tree_order_statistics_node_update, Allocator>;

template <typename Key, typename T, typename Compare = std::less<Key>,
          typename Allocator = std::allocator<std::pair<const Key, T>>>
using ordered_map =
    __gnu_pbds::tree<Key, T, Compare, __gnu_pbds::rb_tree_tag,
                     __gnu_pbds::tree_order_statistics_node_update, Allocator>;

#endif

template <typename Fun>
class y_combinator_result {
 public:
  template <typename T>
  explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }

 private:
  Fun fun_;
};

template <typename Fun>
decltype(auto) y_combinator(Fun&& fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::optional<T>& opt);

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);

template <typename... Ts>
std::ostream& operator<<(std::ostream& os, const std::tuple<Ts...>& t);

template <typename Container,
          std::enable_if_t<!std::is_convertible_v<Container, std::string_view>,
                           typename Container::const_iterator>* = nullptr>
std::ostream& operator<<(std::ostream& os, const Container& c);

template <typename ContainerAdaptor,
          typename ContainerAdaptor::container_type* = nullptr>
std::ostream& operator<<(std::ostream& os, const ContainerAdaptor& a);

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::optional<T>& opt) {
  return opt ? os << *opt : os << "nullopt";
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  return os << '{' << p.first << ", " << p.second << '}';
}

template <typename... Ts>
std::ostream& operator<<(std::ostream& os, const std::tuple<Ts...>& t) {
  return std::apply(
      [&os](const Ts&... args) -> std::ostream& {
        os << '{';
        int i = 0;
        ((os << (i++ == 0 ? "" : ", ") << args), ...);
        return os << '}';
      },
      t);
}

template <typename Container,
          std::enable_if_t<!std::is_convertible_v<Container, std::string_view>,
                           typename Container::const_iterator>*>
std::ostream& operator<<(std::ostream& os, const Container& c) {
  os << '{';
  for (auto it = c.begin(); it != c.end(); ++it) {
    os << (it == c.begin() ? "" : ", ") << *it;
  }
  return os << '}';
}

template <typename ContainerAdaptor, typename ContainerAdaptor::container_type*>
std::ostream& operator<<(std::ostream& os, const ContainerAdaptor& a) {
  class subadaptor : public ContainerAdaptor {
   public:
    const auto& c() const { return ContainerAdaptor::c; }
  };
  return os << static_cast<const subadaptor&>(a).c();
}

namespace detail {

template <typename... Ts>
void print(std::ostream& os, int line, std::string_view keys,
           const Ts&... vals) {
  if constexpr (sizeof...(Ts) == 0) {
    os << "  " << line << " |" << std::endl;
  } else {
    std::vector<std::string_view> key_list;
    key_list.reserve(sizeof...(Ts));
    int start = 0, paren = 0;
    for (int i = 0; i < (int)keys.size(); ++i) {
      switch (keys[i]) {
        case '(':
        case '[':
        case '{':
          ++paren;
          break;
        case ')':
        case ']':
        case '}':
          --paren;
          break;
        case ',':
          if (paren == 0) {
            key_list.push_back(keys.substr(start, i - start));
            start = i;
          }
          break;
      }
    }
    key_list.push_back(keys.substr(start));
    assert(key_list.size() == sizeof...(Ts));
    os << "  " << line << " | ";
    int i = 0;
    ((os << key_list[i++] << " = " << vals), ...);
    os << std::endl;
  }
}

}  // namespace detail

#ifdef TYLER
#define debug(...) \
  detail::print(std::cerr, __LINE__, #__VA_ARGS__ __VA_OPT__(, ) __VA_ARGS__)
#else
#define debug(...) ((void)0)
#endif

constexpr int MODULUS = 1'000'000'007;

template <const int& Modulus = MODULUS>
class mod_int {
 public:
  constexpr mod_int() : val_(0) {}

  template <typename T>
  constexpr mod_int(T val) : val_((int)(val % Modulus)) {
    static_assert(std::is_integral_v<T>);
    if (val_ < 0) {
      val_ += Modulus;
    }
  }

  static constexpr int modulus() { return Modulus; }

  template <typename T>
  constexpr explicit operator T() const {
    return (T)val_;
  }

  constexpr mod_int& operator++() {
    if (++val_ == Modulus) {
      val_ = 0;
    }
    return *this;
  }

  constexpr mod_int operator++(int) {
    mod_int t = *this;
    ++*this;
    return t;
  }

  constexpr mod_int& operator--() {
    if (val_ == 0) {
      val_ = Modulus;
    }
    --val_;
    return *this;
  }

  constexpr mod_int operator--(int) {
    mod_int t = *this;
    --*this;
    return t;
  }

  constexpr mod_int& operator+=(mod_int other) {
    if ((val_ += other.val_) >= Modulus) {
      val_ -= Modulus;
    }
    return *this;
  }

  constexpr mod_int& operator-=(mod_int other) {
    if ((val_ -= other.val_) < 0) {
      val_ += Modulus;
    }
    return *this;
  }

  constexpr mod_int& operator*=(mod_int other) {
    val_ = (int)((long long)val_ * other.val_ % Modulus);
    return *this;
  }

  constexpr mod_int& operator/=(mod_int other) { return *this *= inv(other); }

  friend constexpr mod_int operator+(mod_int mi) { return mi; }

  friend constexpr mod_int operator-(mod_int mi) {
    if (mi.val_ != 0) {
      mi.val_ = Modulus - mi.val_;
    }
    return mi;
  }

  friend constexpr mod_int operator+(mod_int lhs, mod_int rhs) {
    return lhs += rhs;
  }

  friend constexpr mod_int operator-(mod_int lhs, mod_int rhs) {
    return lhs -= rhs;
  }

  friend constexpr mod_int operator*(mod_int lhs, mod_int rhs) {
    return lhs *= rhs;
  }

  friend constexpr mod_int operator/(mod_int lhs, mod_int rhs) {
    return lhs /= rhs;
  }

  friend constexpr bool operator==(mod_int lhs, mod_int rhs) {
    return lhs.val_ == rhs.val_;
  }

  friend constexpr bool operator!=(mod_int lhs, mod_int rhs) {
    return lhs.val_ != rhs.val_;
  }

  friend constexpr bool operator<(mod_int lhs, mod_int rhs) {
    return lhs.val_ < rhs.val_;
  }

  friend constexpr bool operator<=(mod_int lhs, mod_int rhs) {
    return lhs.val_ <= rhs.val_;
  }

  friend constexpr bool operator>(mod_int lhs, mod_int rhs) {
    return lhs.val_ > rhs.val_;
  }

  friend constexpr bool operator>=(mod_int lhs, mod_int rhs) {
    return lhs.val_ >= rhs.val_;
  }

  friend std::ostream& operator<<(std::ostream& os, mod_int mi) {
    return os << mi.val_;
  }

  friend std::istream& operator>>(std::istream& is, mod_int& mi) {
    long long val;
    is >> val;
    mi = mod_int(val);
    return is;
  }

  friend constexpr mod_int inv(mod_int mi) {
    int a = mi.val_, b = Modulus;
    int x = 0, xx = 1;
    while (a != 0) {
      int q = b / a;
      int t = a;
      a = b - q * a;
      b = t;
      t = xx;
      xx = x - q * xx;
      x = t;
    }
    return mod_int(x);
  }

  template <typename T>
  friend constexpr mod_int pow(mod_int base, T expo) {
    static_assert(std::is_integral_v<T>);
    if (expo < 0) {
      base = inv(base);
      expo = -expo;
    }
    mod_int power = 1;
    for (; expo != 0; expo >>= 1) {
      if (expo & 1) {
        power *= base;
      }
      base *= base;
    }
    return power;
  }

 private:
  int val_;
};

template <typename T>
class matrix {
 public:
  matrix(int m, int n, const T& val = T()) : m_(m), n_(n), data_(m * n, val) {}

  matrix(std::initializer_list<std::initializer_list<T>> data)
      : m_((int)data.size()), n_((int)data.begin()->size()) {
    data_.reserve(m_ * n_);
    for (const std::initializer_list<T>& row : data) {
      assert((int)row.size() == n_);
      std::copy(row.begin(), row.end(), std::back_inserter(data_));
    }
  }

  static matrix identity(int n) {
    matrix mat(n, n);
    for (int i = 0; i < n; ++i) {
      mat[i][i] = 1;
    }
    return mat;
  }

  int size1() const { return m_; }

  int size2() const { return n_; }

  T* operator[](int i) { return data_.data() + i * n_; }

  const T* operator[](int i) const { return data_.data() + i * n_; }

  matrix& operator+=(const matrix& other) {
    assert(m_ == other.m_ && n_ == other.n_);
    for (int i = 0; i < (int)data_.size(); ++i) {
      data_[i] += other.data_[i];
    }
    return *this;
  }

  matrix& operator-=(const matrix& other) {
    assert(m_ == other.m_ && n_ == other.n_);
    for (int i = 0; i < (int)data_.size(); ++i) {
      data_[i] -= other.data_[i];
    }
    return *this;
  }

  matrix& operator*=(const matrix& other) { return *this = *this * other; }

  matrix& operator*=(const T& val) {
    for (T& d : data_) {
      d *= val;
    }
    return *this;
  }

  matrix& operator/=(const T& val) {
    for (T& d : data_) {
      d /= val;
    }
    return *this;
  }

  friend matrix operator+(matrix lhs, const matrix& rhs) { return lhs += rhs; }

  friend matrix operator-(matrix lhs, const matrix& rhs) { return lhs -= rhs; }

  friend matrix operator*(const matrix& lhs, const matrix& rhs) {
    assert(lhs.n_ == rhs.m_);
    matrix prod(lhs.m_, rhs.n_);
    for (int i = 0; i < lhs.m_; ++i) {
      for (int j = 0; j < rhs.n_; ++j) {
        for (int k = 0; k < lhs.n_; ++k) {
          prod[i][j] += lhs[i][k] * rhs[k][j];
        }
      }
    }
    return prod;
  }

  friend matrix operator*(matrix lhs, const T& val) { return lhs *= val; }

  friend matrix operator*(const T& val, matrix rhs) { return rhs *= val; }

  friend matrix operator/(matrix lhs, const T& val) { return lhs /= val; }

  friend bool operator==(const matrix& lhs, const matrix& rhs) {
    return lhs.m_ == rhs.m_ && lhs.data_ == rhs.data_;
  }

  friend bool operator!=(const matrix& lhs, const matrix& rhs) {
    return !(lhs == rhs);
  }

  friend std::ostream& operator<<(std::ostream& os, const matrix& mat) {
    os << '{';
    for (int i = 0; i < mat.m_; ++i) {
      os << (i == 0 ? "" : ", ") << '{';
      for (int j = 0; j < mat.n_; ++j) {
        os << (j == 0 ? "" : ", ") << mat[i][j];
      }
      os << '}';
    }
    return os << '}';
  }

  template <typename U>
  friend matrix pow(matrix base, U expo) {
    static_assert(std::is_integral_v<U>);
    matrix power = identity(base.m_);
    for (; expo > 0; expo >>= 1) {
      if (expo & 1) {
        power *= base;
      }
      base *= base;
    }
    return power;
  }

 private:
  int m_, n_;
  std::vector<T> data_;
};

// Berlekamp–Massey algorithm.
template <const int& Modulus = MODULUS>
class linear_recur {
 public:
  linear_recur(const std::vector<mod_int<Modulus>>& seq)
      : coeff_(0, 0), seq_(0, 0) {
    int prev_i = -1;
    mod_int<Modulus> prev_diff = 1;
    std::vector<mod_int<Modulus>> prev_coeff = {1}, coeff = {1};
    for (int i = 0; i < (int)seq.size(); ++i) {
      mod_int<Modulus> diff;
      for (int j = 0; j < (int)coeff.size(); ++j) {
        diff += coeff[j] * seq[i - j];
      }
      if (diff == 0) {
        continue;
      }
      int offset = i - prev_i;
      mod_int<Modulus> q = diff / prev_diff;
      if (prev_coeff.size() + offset <= coeff.size()) {
        for (int j = 0; j < (int)prev_coeff.size(); ++j) {
          coeff[j + offset] -= q * prev_coeff[j];
        }
        continue;
      }
      std::vector<mod_int<Modulus>> next_coeff(prev_coeff.size() + offset);
      std::copy(coeff.begin(), coeff.end(), next_coeff.begin());
      for (int j = 0; j < (int)prev_coeff.size(); ++j) {
        next_coeff[offset + j] -= q * prev_coeff[j];
      }
      prev_i = i;
      prev_diff = diff;
      prev_coeff = std::move(coeff);
      coeff = std::move(next_coeff);
    }
    int n = (int)coeff.size() - 1;
    coeff_ = matrix<mod_int<Modulus>>(n, n);
    for (int i = 0; i < n - 1; ++i) {
      coeff_[i][i + 1] = 1;
    }
    for (int j = 0; j < n; ++j) {
      coeff_[n - 1][j] = -coeff[n - j];
    }
    seq_ = matrix<mod_int<Modulus>>(n, 1);
    std::copy_n(seq.begin(), n, seq_[0]);
  }

  template <typename T>
  mod_int<Modulus> solve(T n) const {
    int m = seq_.size1();
    if (n < m) {
      return seq_[n][0];
    }
    return (pow(coeff_, n - m + 1) * seq_)[m - 1][0];
  }

 private:
  matrix<mod_int<Modulus>> coeff_, seq_;
};

vector<mod_int<>> brute_force(int N) {
  vector<mod_int<>> seq;
  for (int n = 0; n <= N; ++n) {
    mod_int<> sum;
    for (int s1 = 0; s1 < n; ++s1) {
      for (int s2 = s1 + 1; s1 + s2 < n; ++s2) {
        for (int n1 = 0; s1 + s2 + n1 < n; ++n1) {
          for (int n2 = n1 + 1; s1 + s2 + n1 + n2 < n; ++n2) {
            for (int u1 = 0; s1 + s2 + n1 + n2 + u1 < n; ++u1) {
              for (int u2 = u1 + 1; s1 + s2 + n1 + n2 + u1 + u2 < n; ++u2) {
                for (int k1 = 0; s1 + s2 + n1 + n2 + u1 + u2 + k1 < n; ++k1) {
                  for (int k2 = k1 + 1;
                       s1 + s2 + n1 + n2 + u1 + u2 + k1 + k2 < n; ++k2) {
                    for (int e1 = 0;
                         s1 + s2 + n1 + n2 + u1 + u2 + k1 + k2 + e1 < n; ++e1) {
                      for (int e2 = e1 + 1;
                           s1 + s2 + n1 + n2 + u1 + u2 + k1 + k2 + e1 + e2 <= n;
                           ++e2) {
                        sum += mod_int<>(s2 - s1) * mod_int<>(n2 - n1) *
                               mod_int<>(u2 - u1) * mod_int<>(k2 - k1) *
                               mod_int<>(e2 - e1);
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    seq.push_back(sum);
  }
  return seq;
}

int main() {
  auto start_time = std::chrono::steady_clock::now();
  std::mt19937 thanos(
      (std::uint_fast32_t)start_time.time_since_epoch().count());
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.precision(24);
  // vector<mod_int<>> seq = brute_force(60);
  vector<mod_int<>> seq = {
      0,         0,         0,         0,         0,         1,
      11,        71,        341,       1346,      4598,      14038,
      39138,     101193,    245443,    563447,    1232837,   2585672,
      5222552,   10198232,  19316488,  35588718,  63933498,  112225058,
      192839398, 324900532, 537499132, 874246012, 399637805, 207858088,
      434820093, 274485959, 780358,    996765147, 793168065, 118878018,
      966647141, 677996797, 52230779,  485540255, 147468710, 203524158,
      94513877,  885277100, 697944950, 247718575, 502478077, 491383141,
      292066399, 231133366, 338549256, 103211098, 584671766, 944719442,
      472440689, 187649773, 120294030, 377814774, 128625144, 648062132,
      593580804};
  linear_recur recur(seq);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    cout << recur.solve(n) << '\n';
  }
  return 0;
}

Measured memory_bytes: 3644