21273번 - Inverse Problem 다국어

You are given an integer $N$ and an integer sequence $X$ of length $M$. Count, modulo $998244353$, the number of permutations $P = (P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$ that satisfy the following condition:

• The lexicographically smallest subsequence of $P$ of length $M$ coincides with $X$.

The first line contains integers $N$ ($1 \leq N \leq 250000$) and $M$ ($1 \leq M \leq N$).

The second line contains integers $X_1,X_2,\ldots,X_M$ ($1 \leq X_i \leq N$, $X_i \neq X_j$ for all $i \neq j$).

Print the answer.