Good Permutations

Problem Description

For every permutation $a$ of length $n$, we can build a graph from it in the following two ways:

1. For each $1 \le i \le n$, find the largest $j$ with $1 \le j < i$ and $a_j > a_i$, and add an undirected edge between $i$ and $j$.
2. For each $1 \le i \le n$, find the smallest $j$ with $i < j \le n$ and $a_j > a_i$, and add an undirected edge between $i$ and $j$.

Note that the edges are built between the corresponding indices $i, j$.

How many permutations $a$ of length $n$ are there such that the resulting graph contains a cycle?

The number of permutations may be very large; output it modulo $10^9 + 7$.

Input Format

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

Lines $2$ to $T + 1$ each give one integer $n$ ($3 \le n \le 10^6$), the length of the permutation.

Output Format

Output, modulo $10^9 + 7$, the number of permutations satisfying the condition.

Sample Input

1
4

Sample Output

16