Problem Description

Mr. Li buys a circular strawberry cake on his birthday, and the pastry chef puts $n$ identical strawberries around the cake evenly. Now Mr. Li wants to divide the cake following the rules below:

• Each cutting track must be a segment connecting two strawberries.
• Any two cutting tracks cannot intersect strictly inside the cake, but they may share a common strawberry.

Note that cutting tracks are allowed to connect two adjacent strawberries, and Mr. Li can also do nothing.

You are asked to help Mr. Li calculate the number of different ways in cutting the cake. Two ways are regarded as the same if they coincide after rotating the cake. Since the answer could be very large, you only need to tell him the answer modulo $1000000007$.

Input Format

The first line contains an integer $T~(1 \le T \le 10^5)$, the number of test cases.

Each of the test cases contains an integer $n~(2 \leq n \leq 10^6)$, the number of strawberries.

Output Format

For each test case, output an integer denotes the number of different ways of cutting the cake modulo $1000000007$.

2 
2 
3

2
4

Hint

The following figure shows the $4$ ways of cutting the cake with $3$ strawberries.

:::align{center} :::