Score : $700$ points

问题陈述

给定一个正整数 $N$ 和一个包含 $M$ 个非负整数的序列 $A = (A_{1}, A_{2}, \dots, A_{M})$。

这里，$A$ 中的所有元素都是介于 $0$ 和 $N-1$ 之间的不同整数。

找出排列 $P$ 的数量，模 $998244353$，满足以下条件的 $(0, 1, \dots, N-1)$：

• 在将序列 $B = (B_{1}, B_{2}, \dots, B_{N})$ 初始化为 $P$ 后，通过重复以下操作若干次，可以使 $B = A$：
  • 选择 $l$ 和 $r$ 使得 $1 \leq l \leq r \leq |B|$，如果 $\mathrm{mex}(\{B_{l}, B_{l+1}, \dots, B_{r}\})$ 包含在 $B$ 中，则将其从 $B$ 中移除。

什么是 $\mathrm{mex}(X)$？对于有限的非负整数集合 $X$，$\mathrm{mex}(X)$ 定义为不在 $X$ 中的最小非负整数。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a positive integer $N$ and a sequence of $M$ non-negative integers $A = (A_{1}, A_{2}, \dots, A_{M})$.

Here, all elements of $A$ are distinct integers between $0$ and $N-1$, inclusive.

Find the number, modulo $998244353$, of permutations $P$ of $(0, 1, \dots, N-1)$ that satisfy the following condition.

• After initializing a sequence $B = (B_{1}, B_{2}, \dots, B_{N})$ to $P$, it is possible to make $B = A$ by repeating the following operation some number of times:
  • Choose $l$ and $r$ such that $1 \leq l \leq r \leq |B|$, and if $\mathrm{mex}(\{B_{l}, B_{l+1}, \dots, B_{r}\})$ is contained in $B$, remove it from $B$.

What is $\mathrm{mex}(X)$? For a finite set $X$ of non-negative integers, $\mathrm{mex}(X)$ is defined as the smallest non-negative integer that is not in $X$.

Constraints

• $1 \leq M \leq N \leq 500$
• $0 \leq A_{i} < N$
• All elements of $A$ are distinct.
• All input values are integers.

Input

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

$N$ $M$

$A_{1}$ $A_{2}$ $\cdots$ $A_{M}$

Output

Print the answer.

Sample Input 1

4 2
1 3

Sample Output 1

8

After initializing $B = (2, 1, 0, 3)$, it is possible to make $B = A$ using the following steps:

• Choose $(l, r) = (2, 4)$, remove $\mathrm{mex}(\{1, 0, 3\}) = 2$ from $B$, making $B = (1, 0, 3)$.
• Choose $(l, r) = (3, 3)$, remove $\mathrm{mex}(\{3\}) = 0$ from $B$, making $B = (1, 3)$.

Thus, $P = (2, 1, 0, 3)$ satisfies the condition.

There are eight permutations $P$ that satisfy the condition, including the above, so print $8$.

Sample Input 2

4 4
0 3 2 1

Sample Output 2

1

Only $P = (0, 3, 2, 1)$ satisfies the condition.

Sample Input 3

16 7
9 2 4 0 1 6 7

Sample Output 3

3520

Sample Input 4

92 4
1 67 16 7

Sample Output 4

726870122

Find the count modulo $998244353$.