P15740 [JAG 2024 Summer Camp #2] Linear Time Inversion Number

Given a permutation $\boldsymbol{P}$ of length $N$, Alice uses the inversion number as a measure of how close $\boldsymbol{P}$ is to the permutation $(1, 2, \ldots, N)$, while Bob uses the metric $\frac{1}{2} \sum_{i=1}^{N} |P_i - i|$. Here, the inversion number is the number of pairs $(i, j)$ such that $i < j$ and $P_i > P_j$. Given a sequence $\boldsymbol{A} = (A_1, A_2, \ldots, A_K)$ of length $K$, there are $(N - K)!$ permutations of length $N$ that have $\boldsymbol{A}$ as their prefix. Find the number of these permutations for which Alice's metric and Bob's metric are equal, and return the result modulo $998,244,353$.

The input is given in the following format: $$ \begin{aligned} &N \ K \\ &A_1 \ A_2 \ \ldots \ A_K \end{aligned} $$ - $1 \leq N \leq 200,000$ - $0 \leq K \leq N$ - $1 \leq A_i \leq N \quad (1 \leq i \leq K)$ - $A_i \neq A_j \quad (i \neq j)$ - All input values are integers.

Output the answer.