## Algorithm

B. Emordnilap
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation of length n is an array consisting of n distinct integers from 11 to n in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (n=3�=3 but there is 44 in the array). There are n!=n(n1)(n2)1�!=�⋅(�−1)⋅(�−2)⋅…⋅1 different permutations of length n.

Given a permutation p of n numbers, we create an array a consisting of 2n2� 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 ij such that i<j�<� and ai>aj��>��.

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

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 10000000071000000007 (109+7109+7).

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1t1051≤�≤105). The description of the test cases follows.

Each test case has only one line — the integer n (1n1051≤�≤105).

It is guaranteed that the sum of n over all test cases does not exceed 105105.

Output

For each test case, print one integer — the sum of beauties of all permutations of size n modulo 10000000071000000007 (109+7109+7).

Example
input
Copy
3
1
2
100
output
Copy
0
4
389456655

Note

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

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

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define debug(n) cout<<(n)<<endl;
#define pb push_back
const ll INF = 2e18 + 99;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll res = (n-1)*n;
for(ll i = 1; i <= n; i++){
res = ((res%1000000007)*i)%1000000007;
}
cout<<res<<endl;
}

}
Copy The Code &

Input

cmd
3
1
2
100

Output

cmd
0
4
389456655