L. The Shrine of the Father of Forces
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Shrine of the Father of Forces is a renowned shrine known for its miraculous ability to settle any dispute between two parties. The shrine resolves disputes by asking each party a series of questions, and the party that answers correctly wins the dispute.

Mohanad finds this fascinating and realizes that if he knows the questions in advance, he can always win. Fortunately, Mohanad has discovered the type of questions the shrine will ask. The shrine will ask $$$t$$$ questions, each of which is:

Given an odd integer $$$n$$$, find the number of permutations of size $$$n$$$ that satisfy the following conditions:

  • The values at odd indices are first increasing and then decreasing (they can be just increasing or just decreasing).
  • The values at even indices are less than their neighboring values at odd indices (the first and last indices have only one neighboring value).

Please note that the permutation is 0-indexed

A permutation of $$$n$$$ integers is an array containing all numbers from $$$1$$$ to $$$n$$$ exactly once. For example, the arrays $$$[1], \: [2,1,3], \: [5,4,3,2,1]$$$ are permutations, while the arrays $$$[1,1], \: [100], \: [1,2,4,5]$$$ are not.

Knowing the questions beforehand, Mohanad asked you to help him solve them.

Input

The first line contains one integer $$$t \: (1 \le t \le 10^5)$$$ — the number of test cases.

The first line of each test case consists of a single integer $$$n$$$ $$$(1 \le n \lt 10^5)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$, and $$$n$$$ is an odd integer.

Output

For each testcase, output the number of permutations that satisfy the above conditions, taken modulo $$$10^9 + 7$$$.

Example
Input
5
1
3
5
7
9
Output
1
2
16
176
2560