골목 건설

안드레이의 도시 사람들은 팬데믹 이후 최대한 많이 어울리고 싶어 한다. 도시 지원 기금(FPC)은 가구 사이에 작은 사회적 거품을 만들기 위해 골목을 건설하려고 한다. 골목은 서로 다른 두 집을 잇는 연결이다. 각 집은 같은 동네에 있는 다른 집 하나와 정확히 하나의 골목으로 연결되어야 하며, 골목끼리는 교차할 수 없다. 모든 동네의 주민 수는 짝수이고, 각 동네의 집들은 원형으로 배치되어 있다. 각 동네에서 이 골목들을 지을 수 있는 방법이 몇 가지인지 구하라. 예를 들어 집이 6채인 동네에서는 그림 A.1과 같이 골목을 짓는 방법이 5가지 있다.

그림 A.1: 집이 6채인 동네에서는 골목을 짓는 방법이 5가지 있다. 검은 점은 집을, 선은 가능한 골목을 나타낸다.

안드레이의 도시 주민들이 각 동네에서 골목을 지을 수 있는 방법의 수를 계산하라. 이 수는 매우 클 수 있으므로, 답은 313109로 나눈 나머지를 출력한다.

첫 번째 줄에 동네의 수를 나타내는 정수 $q$ ($1\leq q\leq 10^4$)가 주어진다. 이어지는 $q$개의 줄에는 각각 동네에 있는 집의 수를 나타내는 짝수 $n$ ($2\leq n\leq 10^{18}$)이 하나씩 주어진다.

$q$개의 줄을 출력한다. 각 줄에는 해당 동네에서 골목을 지을 수 있는 방법의 수를 313109로 나눈 나머지를 출력한다.