# Appreciation

/*
 * Problem :: 10422 / 괄호
 *
 * Kind :: Math
 *
 * Insight
 * - D[i] = 길이가 i인 올바른 괄호 문자열의 개수
 *   + D[홀수] = 0
 *   + D[2] = 1  / ()
 *     D[4] = 2  / (())
 *                 ()()
 *     D[6] = 5  / ()(()) ()()()
 *                 (())()
 *                 ((())) (()())
 *     D[8] = 14 / ()()(()) ()()()() ()(())() ()((())) ()(()())
 *                 (())(()) (())()()
 *                 ((()))() (()())()
 *                 (()(())) (()()()) ((())()) (((()))) ((()()))
 *     ...
 *     # D[2] = D[0] * D[0]
 *       D[4] = D[0] * D[2]
 *              + D[2] * D[0]
 *       D[6] = D[0] * D[4]
 *              + D[2] * D[2]
 *              + D[4] * D[0]
 *       D[8] = D[0] * D[6]
 *              + D[2] * D[4]
 *              + D[4] * D[2]
 *              + D[6] * D[0]
 *       ...
 *       -> U_i = 길이 i인 올바른 괄호 문자열
 *          S_j = 길이 j인 올바른 괄호 문자열
 *          T_k = 길이 k인 올바른 괄호 문자열
 *       -> U_2 = (S_0)T_0
 *          U_4 = (S_2)T_0
 *                xor (S_0)T_2
 *          U_6 = (S_4)T_0
 *                xor (S_2)T_2
 *                xor (S_0)T_4
 *          U_8 = (S_6)T_0
 *                xor (S_4)T_2
 *                xor (S_2)T_4
 *                xor (S_0)T_6
 *          ...
 *          => (S_6)T_0 과 (S_4)T_2 에서 겹치는 올바른 괄호 문자열은 없다!
 *             (S_6)T_0 = ((????))
 *             (S_4)T_2 = ((??))()
 *                              ^ <= 7번째 문자가 서로 다르다!
 *          => (S_4)T_2 과 (S_2)T_4 에서 겹치는 올바른 괄호 문자열은 없다!
 *             (S_4)T_2 = ((??))()
 *             (S_2)T_4 = (())(??)
 *                            ^ <= 5번째 문자가 서로 다르다!
 *
 * Point
 * - D[i] * D[j] 에서 Overflow 위험이 있으므로
 *   long 타입을 사용하자
 *
 * - 카탈린 수(Catalan Number)열
 *   + https://suhak.tistory.com/77
 *     # C1 = C0C0
 *       C2 = C0C1 + C1C0
 *       C3 = C0C2 + C1C1 + C2C0
 *       C4 = C0C3 + C1C2 + C2C1 + C3C0
 *       ...
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Process
    long D[5000+1]; /* D[2], D[4], D[6], ... = 카탈란 수열 */
    memset(D, 0, sizeof(D));
    D[0] = 1;
    for (int i=2; i<=5000; i+=2) {
        for (int j=0; j<=i-2; j+=2) {
            D[i] += D[j] * D[i-2-j];
            D[i] %= 1'000'000'007;
        }
    }

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        int L; cin >> L;

        // Control : Output
        cout << D[L] << endl;
    }
}

// Helper Functions
/* None */