Counting Good Permutations

Recently, Little S became fascinated with bubble sort. To keep things simple, she only studies the bubble sort of permutations of the set \(\{1, 2, \dots, n\}\).

The bubble sort algorithm is described as follows:

Input: a permutation \(p[1\dots n]\)
Output: the sorted permutation
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 swap count of bubble sort is defined as the total number of swaps performed. It can be shown that a lower bound for the swap count is \[ \frac{1}{2} \sum_{i=1}^{n} \lvert i - p_i \rvert \] where \(p_i\) is the number at position \(i\) in the permutation \(p\). For convenience, we call a permutation good if its bubble sort swap count equals \(\frac{1}{2}\sum_{i=1}^{n} |i-p_i|\).

Little S is now curious about the distribution of these good permutations. For a given permutation \(q\) of length \(n\), she would like to know how many good permutations are lexicographically strictly greater than \(q\). Since the answer might be huge, output it modulo \(998244353\).

Note on lexicographical order: A permutation \(p\) is lexicographically greater than \(q\) if there exists an index \(i\) such that \(p_j = q_j\) for all \(j < i\) and \(p_i > q_i\).

Mathematical formulation: Given a permutation \(q = [q_1, q_2, \dots, q_n]\) of \(\{1,2,\dots,n\}\), count the number of permutations \(p\) of \(\{1,2,\dots,n\}\) that are good and satisfy \(p\) is lexicographically greater than \(q\). A permutation \(p\) is said to be good if \[ \text{swaps}(p) = \frac{1}{2}\sum_{i=1}^{n} \lvert i-p_i \rvert, \] where \(\text{swaps}(p)\) is the number of adjacent swaps performed by the above bubble sort algorithm.

inputFormat

The input consists of two lines.

The first line contains a single integer \(n\) (the length of the permutation).

The second line contains \(n\) space‐separated integers \(q_1, q_2, \dots, q_n\), denoting the permutation \(q\).

\(1 \le n \le 10\).

outputFormat

Output a single integer: the number of good permutations that are lexicographically strictly greater than \(q\), taken modulo \(998244353\).

sample

3
1 2 3

4