• 올바른 괄호의 갯수는 카탈랑 수 (Catalan number)로 표현되는 대표적인 예제이다.
  • 왜 이게 카탈랑 수가 되는지는, 올바른 괄호의 갯수에 간략히 설명했다
• L이 홀수이면, 올바른 괄호가 만들어질 수 없으니 0을 출력하고 L이 짝수이면, L/2번째 카탈랑 수를 출력하면 된다
• 테스트 케이스가 여러개이므로, 매번 L/2번째 카탈랑 수를 계산하는 것보다, 전처리 단계에서 범위 내의 카탈랑수를 미리 모두 계산해 놓고 (O(n)에 가능하다), 테스트 케이스를 입력받으면서 계산해 놓은 카탈랑 수를 출력해야 효율적이다. 이렇게 하면, O(L+T)에 해결 가능하다.

"""Solution code for "BOJ 10422. 괄호".

- Problem link: https://www.acmicpc.net/problem/10422
- Solution link: http://www.teferi.net/ps/problems/boj/10422
"""

MOD = 1_000_000_007
MAX_SIZE = 25000


def main():
    inv = [0, 1]
    for i in range(2, MAX_SIZE + 3):
        inv.append(-(MOD // i) * inv[MOD % i])
    catalan_nums = [1]
    for i in range(MAX_SIZE):
        catalan_nums.append(2 * (2 * i + 1) * inv[i + 2] * catalan_nums[i] %
                            MOD)

    T = int(input())
    for _ in range(T):
        L = int(input())
        print(0 if L % 2 else catalan_nums[L // 2])


if __name__ == '__main__':
    main()