Description

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$.

Input Format

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 Format

Output the answer.

5 3
2 3 5

1

10 10
3 1 4 5 9 2 6 8 7 10

0

6 0

132