// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

using int64 = long long;



constexpr int DEBUG = 0;



constexpr int64 P = 1000000007;



struct FiniteField {

 private:

  int64 x;

 public:

  FiniteField(int64 raw_x) : x(raw_x) {

    if (x >= P || x < 0) { 

      x %= P;

      if (x < 0) x += P;

    }

  }

  FiniteField() : x(0) {}

  int64 Value() const { return x; }

  inline FiniteField operator+(FiniteField o) const {

    FiniteField r(*this); r += o; return r;

  }

  inline FiniteField operator-(FiniteField o) const {

    FiniteField r(*this); r -= o; return r;

  }

  inline FiniteField operator* (FiniteField o) const {

    FiniteField r(*this); r *= o; return r;

  }

  inline FiniteField operator/ (FiniteField o) const {

    FiniteField r(*this); r /= o; return r;

  }

  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }

  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }

  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }

  void operator/=(FiniteField o) {

    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }

  }

};

ostream& operator<<(ostream& s, const FiniteField& x) { s << x.Value(); return s; }



FiniteField Combination(int a, int b) {

  FiniteField r = 1;

  for (int k = 0; k < b; k++) {

    r *= (a - k);

    r /= (1 + k);

  }

  return r;

}



FiniteField F(int n) {

  FiniteField r = 0;

  for (int x = 0; n - 5 - 2 * x >= 0; x++) {

    r += Combination(x + 4, 4) * Combination(n - 2 * x + 5, 10);

  }

  return r;

}



FiniteField LagrangeInterpolation(const vector<pair<int, FiniteField>>& ps, int x) {

  FiniteField r = 0;

  for (int i = 0; i < ps.size(); i++) {

    const auto [x_i, y_i] = ps[i];

    FiniteField t = 1;

    for (int k = 0; k < ps.size(); k++) {

      if (k == i) continue;

      const auto [x_k, y_k] = ps[k];

      t *= x - x_k;

      t /= x_i - x_k;

    }

    r += t * y_i;

  }

  return r;

}



FiniteField Solve() {

  int n;

  cin >> n;

  if (n <= 4) return 0;



  if (n % 2 == 1) {

    vector<pair<int, FiniteField>> ps;

    for (int x = 5; x < 5 + 2 * 16; x += 2) {

      ps.push_back({x, F(x)});

    }



    FiniteField r = LagrangeInterpolation(ps, n);

    return r;

  } else {

    vector<pair<int, FiniteField>> ps;

    for (int x = 6; x < 6 + 2 * 16; x += 2) {

      ps.push_back({x, F(x)});

    }



    FiniteField r = LagrangeInterpolation(ps, n);

    return r;

  }

}



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);



  int num_cases;

  cin >> num_cases;

  for (int case_id = 0; case_id < num_cases; case_id++) {

    cout << Solve() << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 1.876678060109749x):
#include <bits/stdc++.h>



using namespace std;

using int64 = long long;



constexpr int DEBUG = 0;



constexpr int64 P = 1000000007;



struct FiniteField {

 private:

  int64 x;

 public:

  FiniteField(int64 raw_x) : x(raw_x) {

    if (x >= P || x < 0) {

    x %= P;

    if (x < 0) x += P;

  }

}

  FiniteField() : x(0) {}

  int64 Value() const { return x; }

  inline FiniteField operator+(FiniteField o) const {

    FiniteField r(*this); r += o; return r;

  }

  inline FiniteField operator-(FiniteField o) const {

    FiniteField r(*this); r -= o; return r;

  }

  inline FiniteField operator* (FiniteField o) const {

    FiniteField r(*this); r *= o; return r;

  }

  inline FiniteField operator/ (FiniteField o) const {

    FiniteField r(*this); r /= o; return r;

  }

  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }

  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }

  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }

  void operator/=(FiniteField o) {

    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }

  }

};



ostream& operator<<(ostream& s, const FiniteField& x) {

  s << x.Value();

  return s;

}



// Vector

template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {

  int len = v.size();

  s << "[";

	for (int i = 0; i < len; i++) {

    if (i > 0) s << ", ";

		s << v[i];

  }

  s << "]";

  return s;

}



// Find the n-th term of a sequence defined by a generative function P(x) / Q(x).

// Q(x) is a polynomial of degree k which satisfies Q(0) = 1.

// P(X) is a polynomial of degree at most k - 1.

// The method name follows SymPy.

FiniteField RationalAlgorithm(const vector<FiniteField>& p, const vector<FiniteField>& q, int64 n) {

  if (n == 0) {

    if (p.empty()) return 0;

    return p[0];

  }



  static auto multiply_fn = [](const vector<FiniteField>& p1, const vector<FiniteField>& p2) {

    if (p1.empty() || p2.empty()) return vector<FiniteField>();

    int d1 = p1.size() - 1;

    int d2 = p2.size() - 1;

    vector<FiniteField> r(d1 + d2 + 1);

    for (int i = 0; i <= d1; i++) {

      for (int j = 0; j <= d2; j++) {

        r[i + j] += p1[i] * p2[j];

      }

    }

    return r;

  };



  // Returns P(-x) for a given P(x).

  static auto minus_x_fn = [](const vector<FiniteField>& p) {

    vector<FiniteField> r = p;

    for (int i = 1; i < r.size(); i += 2) {

      r[i] *= -1;

    }

    return r;

  };



  static auto take_even_fn = [](const vector<FiniteField>& p) {

    vector<FiniteField> r;

    for (int i = 0; i < p.size(); i += 2) {

      r.push_back(p[i]);

    }

    return r;

  };



  static auto take_odd_fn = [](const vector<FiniteField>& p) {

    vector<FiniteField> r;

    for (int i = 1; i < p.size(); i += 2) {

      r.push_back(p[i]);

    }

    return r;

  };



  if (n % 2 == 0) {

    return RationalAlgorithm(

        take_even_fn(multiply_fn(p, minus_x_fn(q))),

        take_even_fn(multiply_fn(q, minus_x_fn(q))),

        n / 2);

  } else {

    return RationalAlgorithm(

        take_odd_fn(multiply_fn(p, minus_x_fn(q))),

        take_even_fn(multiply_fn(q, minus_x_fn(q))),

        (n - 1) / 2);

  } 

}



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);



  static auto multiply_fn = [](const vector<FiniteField>& p1, const vector<FiniteField>& p2) {

    if (p1.empty() || p2.empty()) return vector<FiniteField>();

    int d1 = p1.size() - 1;

    int d2 = p2.size() - 1;

    vector<FiniteField> r(d1 + d2 + 1);

    for (int i = 0; i <= d1; i++) {

      for (int j = 0; j <= d2; j++) {

        r[i + j] += p1[i] * p2[j];

      }

    }

    return r;

  };



  vector<FiniteField> f({0, 1});

  vector<FiniteField> g({1, -2, 0, 2, -1});



  vector<FiniteField> p({1});

  vector<FiniteField> q({1});

  for (int i = 0; i < 5; i++) {

    p = multiply_fn(p, f);

    q = multiply_fn(q, g);

  }

  q = multiply_fn(q, {1, -1});



  int t;

  cin >> t;

  for (int i = 0; i < t; i++) {

    int n;

    cin >> n;

    cout << RationalAlgorithm(p, q, n) << endl;

  }

}