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`

##### Subtask

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 |

## Comments