역문제

시간 제한1초메모리 제한1024 MB

난이도: 아직 분류되지 않았습니다
정답자: 아직 제출이 없습니다

문제

정수 $N$ 과 길이가 $M$ 인 정수 수열 $X$ 가 주어진다. $(1,2,\ldots,N)$ 의 순열 $P=(P_1,P_2,\ldots,P_N)$ 중에서, $P$ 의 길이가 $M$ 인 부분수열 가운데 사전순으로 가장 작은 것이 $X$ 와 일치하는 순열의 개수를 구한다. 개수는 $998244353$ 으로 나눈 나머지로 출력한다.

입력

첫째 줄에 정수 $N$ ( $1 \leq N \leq 250000$ )과 $M$ ( $1 \leq M \leq N$ )이 주어진다.

둘째 줄에는 정수 $X_1,X_2,\ldots,X_M$ ( $1 \leq X_i \leq N$ , 모든 $i \neq j$ 에 대해 $X_i \neq X_j$ )이 주어진다.

출력

답을 출력한다.

예제3

예제 1
입력
```
3 2
1 2
```
예상 출력
```
3
```
예제 2
입력
```
10 5
2 7 8 3 6
```
예상 출력
```
0
```
예제 3
입력
```
5 5
1 2 3 4 5
```
예상 출력
```
1
```