MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

The 2020 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

H - Round table

Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)

Consider $ 2\cdot n $ people with $ n $ enemy pairs, Each person has exactly one enemy and the enmity is bi-directional, meaning that, if $ a $ is the enemy of $ b $, then $ b $ is the enemy of $ a $. Enemy pairs are defined as follows, for all $ j $ ($ 1 \leq j \leq n $), the person $ 2 \cdot j - 1 $ and the person $ 2 \cdot j $ are enemies.

You want to calculate in how many ways it is possible to distribute them on a large circular table with $ 2 \cdot n $ seats, so that there are no 2 enemies sitting next to each other.

The seats are numbered from $ 1 $ to $ 2 \cdot n $. The seats of positions $ i $ and $ i + 1 $ are adjacent for all $ 1 \leq i <2 \cdot n $. The seats $ 1 $ and $ 2 \cdot n $ are also adjacent. Two distributions are considered different if they have at least one seat occupied by different people in each distribution.

For example:
We have 4 people and the enemy pairs are $ (1, 2) $ and $ (3, 4) $. There are 8 different ways to place them around the table:

       $\bullet (1, 3, 2, 4) \qquad \qquad \bullet (2, 3, 1, 4)\qquad \qquad \bullet(3, 1, 4, 2)\qquad \qquad \bullet (4, 1, 3, 2)$ 
       $\bullet (1, 4, 2, 3)\qquad \qquad \bullet (2, 4, 1, 3) \qquad \qquad \bullet(3, 2, 4, 1)\qquad \qquad \bullet (4, 2, 3, 1)$

Input

The first line of the input contains an integer $ t $ $ (1 \leq t \leq 10^5) $, the number of cases to process. The next $ t $ lines describe the test cases, each with an integer $ n $ $ (1 \leq n \leq 10^5) $, the number of enemy pairs.

Output

For each test case you should print a line with the number of possible distributions. Since this number can be very large, print the remainder left by dividing it by $ 10^9 + 7$.

Sample test(s)

Input
4 1 2 4 99999
Output
0 8 11904 720034323