Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Emordnilap

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array). There are $$$n! = n \cdot (n-1) \cdot (n - 2) \cdot \ldots \cdot 1$$$ different permutations of length $$$n$$$.

Given a permutation $$$p$$$ of $$$n$$$ numbers, we create an array $$$a$$$ consisting of $$$2n$$$ numbers, which is equal to $$$p$$$ concatenated with its reverse. We then define the beauty of $$$p$$$ as the number of inversions in $$$a$$$.

The number of inversions in the array $$$a$$$ is the number of pairs of indices $$$i$$$, $$$j$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$.

For example, for permutation $$$p = [1, 2]$$$, $$$a$$$ would be $$$[1, 2, 2, 1]$$$. The inversions in $$$a$$$ are $$$(2, 4)$$$ and $$$(3, 4)$$$ (assuming 1-based indexing). Hence, the beauty of $$$p$$$ is $$$2$$$.

Your task is to find the sum of beauties of all $$$n!$$$ permutations of size $$$n$$$. Print the remainder we get when dividing this value by $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

Each test case has only one line — the integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print one integer — the sum of beauties of all permutations of size $$$n$$$ modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Example

Input

312100

Output

0 4 389456655

Note

For the first test case of the example, $$$p = [1]$$$ is the only permutation. $$$a = [1, 1]$$$ has $$$0$$$ inversions.

For the second test case of the example, the permutations are $$$[1, 2]$$$ and $$$[2, 1]$$$. Their respective $$$a$$$ arrays are $$$[1, 2, 2, 1]$$$ and $$$[2, 1, 1, 2]$$$, both of which have $$$2$$$ inversions.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/08/2023 19:02:25 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|