====== Alleys Construction ======

===== 풀이 =====
  * 문제 자체는 [[ps:problems:boj:1670]]과 동일하다. n/2번째 [[ps:tutorial:카탈랑 수]]를 구하면 된다.
  * 난이도를 올리는 것은, 이 카탈랑 수를 313109 로 나눈 나머지를 구하는 것. 313109는 소수이기는 하지만, n보다 작을 수 있기 때문에, 일반적인 방법으로는 안되고, [[ps:이항 계수#N보다 작은 소수로 나눈 나머지]] 를 구하는 방법을 써야 한다
  * 뤼카의 정리를 이용해서 처리하면, 시간복잡도는 O(P)의 전처리 이후, 각 쿼리를 O(logn/logP)에 계산할 수 있다 (P=303109)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 33229. Alleys Construction".

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

Tags: [catalan]
"""

import sys
from teflib import combinatorics


MOD = 313109


def main():
    cc = combinatorics.CombCalculatorForSmallMod(MOD)

    q = int(sys.stdin.readline())
    for _ in range(q):
        n = int(sys.stdin.readline())
        print(cc.comb(n, n // 2) * pow(n // 2 + 1, -1, MOD) % MOD)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#CombCalculatorForSmallMod|teflib.combinatorics.CombCalculatorForSmallMod]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}