H. Obada's Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The judges were overwhelmed by how much work they need to put on the contest, especially that most of them either have jobs, exams or both. They were trying hard to come up with problem ideas and then work on them.

Obada, this problem's author, told the judges he had a cool problem idea and he'll add it soon. A few days before the contest, he finally added the problem.

For a permutation $$$p$$$ of length $$$n$$$. You can do the following operation any number of times:

  • Choose two integer numbers $$$l$$$ and $$$r$$$ $$$(1 \le l_i < r_i \le n)$$$, where $$$l$$$ should be greater than $$$l$$$ chosen in the previous operation. More formally, in the $$$i-th$$$ operation where $$$i > 1$$$, $$$l_i$$$ > $$$l_{i-1}$$$.
  • Reverse the subarray $$$a_l, a_{l+1}, \dots a_r$$$.

The cost of a permutation $$$p$$$ is the minimum number of operations you need to do so that $$$p$$$ is sorted in ascending order.

Given an integer number $$$n$$$, find the sum of costs over all permutations of length $$$n$$$ modulo $$$10^9 + 7$$$.

Input

The first line of the input contains a single integer number $$$t$$$ $$$(1 \le t \le 10^5)$$$. The number of test cases.

The first line of each test case contains a single integer number $$$n$$$ $$$(1 \le n \le 10^6)$$$. The length of the permutations

Output

For each test case print a single line containing a single integer number. The sum of costs over all permutations of length $$$n$$$ modulo $$$10^9 + 7$$$.

Example
Input
3
1
5
7
Output
0
326
22212