시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 3 2 2 66.667%

문제

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.

예제 입력 1

3 2
1 2

예제 출력 1

3

예제 입력 2

10 5
2 7 8 3 6

예제 출력 2

0

예제 입력 3

5 5
1 2 3 4 5

예제 출력 3

1