#435 Reading KakaoTalk

Statement

Statement language

There are $N$ people and $M$ messages in a chat room. The messages are numbered $1,2,\cdots,M$ from oldest to newest.

Message $i$ was written by person $A_i$ , and exactly $B_i$ people have read message $i$ .

For each person $p$ , let $C_p$ be the index of the last message read by that person. If $C_p=0$ , the person has read no messages. If , the person has read every message and has not read messages .

A person is considered to have read every message up to each message they wrote. Therefore, $C_{A_i}\ge i$ must hold for every $i$ .

A sequence $C=(C_1,C_2,\cdots,C_N)$ is if all of the following conditions hold.

$0\le C_p\le M$ ( $1\le p\le N$ ).
().

The input sequence $B$ satisfies $B_1\ge B_2\ge\cdots\ge B_M$ . It is also guaranteed that at least one valid sequence exists.

Find the number of valid sequences $C$ modulo $998\,244\,353$ .

Input

The input is given from Standard Input in the following format:

$N\ M$ $A_1\ A_2\ \cdots\ A_M$

Output

Print the number of valid sequences $C$ modulo $998\,244\,353$ .

Constraints

$1\le N\le 200\,000$ .
$1\le M\le 200\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	8	$N\le 7$ and $M\le 7$ .
2	45	$N\le 2\,000$ and .

Samples

Sample 1

Input

2
2
1

Output

1

Sample 2

Input

2
1
2

Output

6

Sample 3

Input

2
1
1

Output

2