A. Array Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Little H is so boring that he wants to generate an array of length $$$n$$$.

Little H uses the following method to generate the array.

  • Suppose the current array length is $$$m(m \lt n)$$$. Then he will randomly generate a number $$$x$$$ from $$$[1, n - m]$$$. Then he will follow the ordered permutation of $$$[1, x]$$$(such as $$$x = 3$$$, the ordered permutation is $$$[1, 2, 3]$$$) after the array.
  • If the length of the array after the append operation is completed is $$$n$$$，then finish the entire process, otherwise repeat the above steps.

Now little H want to know how many different arrays there are for a certain $$$n$$$。

Due to the limited ability of counting little H, you just need to output the answer modulo $$$10^9 + 7$$$.

Input

There are several test cases.

The first line contains a single integer $$$T(1 \leq T \leq 10^3)$$$, denoting the number of test cases. Then follow all the test cases.

For each test case, only one line which contains a single integer $$$n(1 \leq n \leq 10^6)$$$, denoting the length of the array little H wants to generate.

Output

For each test case, print a integer in one line which denoting the answer.

Example
Input
3
1
100
1000000
Output
1
988185646
617521033