408071: GYM102978 I 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.

3 2
1 2

3

10 5
2 7 8 3 6

0

5 5
1 2 3 4 5

1