Codeforcess Solution 1777-B B. Emordnilap ,C++, Java, Js and Python

Algorithm

A 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 \dots \cdot 1$ different permutations of length $n$ .

Given a permutation $p$ of $n$ numbers, we create an array $a$ consisting of $2 n$ 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 \leq t \leq 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
Copy
3
1
2
100
output
Copy
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.

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 & Try With Live Editor

Input

–

cmd

3
1
2
100

Output

–

cmd

0
4
389456655

Demonstration

Codeforcess Solution 1777-B B. Emordnilap ,C++, Java, Js and Python,1777-B,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 1 year ago 318 0