Limits 1s, 512 MB

This Problem is very straightforward. Let’s define a function InvCnt(p)InvCnt(p) where pp is a permutation of length nn. Definition of InvCnt(p)InvCnt(p) is the minimum number of swaps needed to make the permutation pp sorted, and you are allowed to swap only adjacent elements.

A permutation is an array of length nn, consisting of each of the integers from 11 to nn in some order.

For example, a permutation of length 44 is —

Then we need to do the following operations to sort the permutation —

So we need a total of 55 swap operations to make pp sorted.

Now you are given an integer nn. You have to print the total sumsum of InvCnt(p)InvCnt(p) for all permutations of length nn. More formally, if we define a set SS consisting of all permutations of length nn. Then we need to calculate

pSInvCnt(p)mod109+7\displaystyle\sum_{p \in S} ^{}InvCnt(p) \mod 10^9+7

Input

Each set of tests contains multiple test cases.

The first line of the input contains a single integer tt — which represents the number of test cases.

Next, tt lines of the input contain a single integer nn — representing the length of the permutation.

1t1061\leq t \leq 10^6

1n 1071 ≤ n ≤  10^7

Output

For each test case print the case number and a single integer  — the total summod109+7sum \mod 10^9 + 7 from the problem statement.

Sample

InputOutput
4
3
2
4
17
Case 1: 9
Case 2: 1
Case 3: 72
Case 4: 941220792

Consider the first testcase.

For nn == 33. We have 66 different permutations. And

InvCnt({1,2,3})InvCnt(\{1,2,3\})==00

InvCnt({1,3,2})InvCnt(\{1,3,2\})== 11

InvCnt({2,1,3})InvCnt(\{2,1,3\})==11

InvCnt({2,3,1})InvCnt(\{2,3,1\})==22

InvCnt({3,1,2})InvCnt(\{3,1,2\})==22

InvCnt({3,2,1})InvCnt(\{3,2,1\})==33

So totalsumtotal sum is 0+1+1+2+2+3=90 + 1 + 1 + 2 + 2 + 3 = 9

Submit

Login to submit.

Statistics

67% Solution Ratio
dip_BRUREarliest, 5M ago
Tanvir_580Fastest, 0.1s
dip_BRURLightest, 67 MB
pathanShortest, 484B
Toph uses cookies. By continuing you agree to our Cookie Policy.