Problem Background

Please note that there are test cases with $n = 0$.

Problem Description

Recently, Xiao S has developed a strong interest in bubble sort. For simplicity, Xiao S is studying bubble sort on permutations of the numbers from 1 to n.

Below is the algorithm description for bubble sort.

Input: A permutation p[1...n] of length n
Output: The sorted result of p.
for i = 1 to n do
    for j = 1 to n - 1 do
        if(p[j] > p[j + 1])
            swap p[j] and p[j + 1]

The number of swaps in bubble sort is defined as the number of swap operations executed. It can be proven that a lower bound for the number of swaps is $\frac{1}{2} \sum_{i=1}^n |i - p_i|$, where $p_i$ is the number at the $i$-th position in the permutation $p$. If you are interested in the proof, please refer to the hints.

Xiao S is focusing on permutations of length $n$ that achieve exactly $\frac{1}{2} \sum_{i=1}^n |i - p_i|$ swaps (hereafter, for convenience, we refer to all such permutations as "good" permutations). He further wonders how many and how densely these permutations are distributed.

Xiao S wants to calculate the number of "good" permutations that are lexicographically strictly greater than a given permutation $q$ of length $n$. However, he is unable to do this and seeks your help. Considering the answer may be very large, you only need to output the result modulo $998244353$.

Input Format

The first line of input contains a positive integer $T$, representing the number of test cases.

For each test case, the first line contains a positive integer $n$, with $n \leq 6 \times 10^5$.

The next line contains $n$ positive integers, corresponding to the elements $q_i$ of the permutation $q$, ensuring that the input is a permutation of the numbers from 1 to $n$.

Output Format

The output consists of $T$ lines, each containing an integer.

For each test case, output an integer representing the number of "good" permutations that are lexicographically strictly greater than $q$, modulo $998244353$.

Sample Input and Output

Sample Input #1

1
3
1 3 2

Sample Output #1

3

Sample Input #2

1
4
1 4 2 3

Sample Output #2

9

Notes

Sample 1 Explanation

Among the permutations lexicographically greater than $1 3 2$, all except $3 2 1$ are "good" permutations, hence the answer is $3$.

Data Range

The following table describes the input scale for each test point.

For all data, $T = 5$ (samples may not satisfy this).

Let $n_\mathrm{max}$ denote the maximum value of $n$ in each test case, and $\sum n$ denote the sum of all $n$ values.

Hints

The proof that the lower bound for the number of swaps is $\frac{1}{2} \sum_{i=1}^n |i - p_i|$ is as follows:

Sorting essentially involves moving numbers, so the number of swaps in sorting can be described by the total distance of the movements. For the $i$-th position, if the number at this position in the initial permutation is $p_i$, then we need to move this number to the $p_i$-th position, with a distance of $|i - p_i|$. Thus, the total distance of the movements is $\sum_{i=1}^n |i - p_i|$, and each swap in bubble sort can reduce the total distance by at most 2. Therefore, $\frac{1}{2} \sum_{i=1}^n |i - p_i|$ is a lower bound for the number of swaps in bubble sort.

Not all permutations achieve this lower bound. For example, when $n = 3$, consider the permutation $3 2 1$. The number of swaps after bubble sort is 3, but $\frac{1}{2} \sum_{i=1}^n |i - p_i|$ is only 2.

见题面 Input 部分

见题面 Output 部分