Reduce to one

Consider a list of integers $L$. Initially $L$ contains the integers $1$ through $n$, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in $L$ is not important. You should perform the following operation $n-1$ times:

• Choose two elements of the list, let's denote them by $x$ and $y$. These two elements may be equal.

• Erase the chosen elements from $L$.

• Append the number $x+y+x\cdot y$ to $L$.

At the end, $L$ contains exactly one integer. Find the maximum possible value of this integer. Since the answer may be large, compute it modulo $10^9+7$.

Input

The first line contains the number of test cases $t$. Each of the next $t$ lines contains a single integer $n(1\le n\le 10^6)$.

Output

For each test case, print a single line containing one integer — the maximum possible value of the final number in the list modulo $10^9+7$.

Examples