## NOI '18 Problem 2 - Inverse

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Consider the bubble sort algorithm:

for i = 1 to n do
for j = 1 to n - 1 do
if(p[j] > p[j + 1])
swap(p[j], p[j+1])

Let denote as the number of times the function is called when we run the bubble sort algorithm on permutation . We call a good permutation if . One can prove is a tight lower bound for permutations of length .

You are given an permutation and asked to the number of good permutations of length that is strictly lexicographically larger than . The output might be too large, so you only need to output the answer under modulo

#### Input Specification

The first line contains an integer , the number of test cases.

For each test case,

• The first line contains an integer , which is the length of the permutation.
• The second lines contains integers in the permutation.

#### Output Specification

For each test case, output the answer under modulo

#### Constraints

For all test file, .

is the maximum in a single file. is the sum of is a single file.

#### Sample 1 Input

1
3
1 3 2

#### Sample 1 Output

3

#### Sample 1 Explanation

All permutation lexicographically larger than "" is good except ""

#### Sample 2 Input

1
4
1 4 2 3

#### Sample 2 Output

9

For all data, is satisfied (sample may not be satisfied).

Denote to denote the maximum value of in each set of data, and to denote the sum of for all data.

test point special properties
1 None
2 none
3 None
4 None
5 None
6 None
7 None
8 None
9 None
10 None
11 None
12
13 None
14 None
14 None
16 None
17
18 None
19 None
20 None
21
22 none
23 None
24 None
25 none