Alleys Construction

Time limit1sMemory limit2048 MB

Summary

For each even n, count the non-crossing perfect matchings of n houses on a circle (the Catalan number for n/2) modulo 313109, with n up to 10^18.

Level: Medium6 of 10
Topics: Combinatorics, Number theory, Math
Solved: No attempts yet

Statement

In Andrei's city, people want to socialize as much as possible after the pandemic. The Fund for Providing the City (FPC) has announced that they want to construct alleys to create small social bubbles between households. An alley is a connection between two distinct houses. Each house must be connected with exactly one alley to another house within the same neighbourhood, and the alleys may not intersect. The number of inhabitants of any neighbourhood is even, and the houses in each neighbourhood are arranged in a circle. For each neighbourhood, find in how many ways these alleys can be built. For example, a neighbourhood with six houses has five possible ways to build alleys, as shown in Figure A.1.

Figure A.1: For a neighbourhood of six houses, there are five possible ways to build alleys. Each black dot is a house, and each line is a possible alley.

Calculate the number of ways the inhabitants of Andrei's city can build alleys in each neighbourhood. The number can be very large, so output the answer modulo 313109.

Input

The first line contains a single integer $q$ ( $1\leq q\leq 10^4$ ), the number of neighbourhoods. Each of the next $q$ lines contains one even number $n$ ( $2\leq n\leq 10^{18}$ ), the number of houses in the neighbourhood.

Output

Output $q$ lines. Each line contains the number of ways to build alleys in the corresponding neighbourhood, modulo 313109.

Examples1

Example 1
Input
```
4
6
10
122
50
```
Expected output
```
5
42
256789
182049
```