AT_arc178_d.[ARC178D] Delete Range Mex

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

这里，$A$ 的所有元素都是大于等于 $0$ 且小于 $N$ 的整数，并且互不相同。

请计算有多少个 $(0,1,\dots,N-1)$ 的排列 $P$ 满足以下条件，并输出答案对 $998244353$ 取模后的结果。

• 将数列 $B=(B_{1},B_{2},\dots,B_{N})$ 用 $P$ 初始化后，可以通过任意次数以下操作将 $B$ 变为 $A$：
  • 选择满足 $1\leq l\leq r\leq |B|$ 的 $l,r$，如果 $\mathrm{mex}(\{B_{l},B_{l+1},\dots,B_{r}\})$ 在 $B$ 中出现，则将其从 $B$ 中删除。

$\mathrm{mex}(X)$ 的定义如下：对于由非负整数组成的有限集合 $X$，$\mathrm{mex}(X)$ 是满足 $x\notin X$ 的最小非负整数 $x$。

输入从标准输入中给出，格式如下：

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

请输出答案。

限制条件

• $1\leq M\leq N\leq 500$
• $0\leq A_{i}<N$
• $A$ 的元素互不相同
• 所有输入均为整数

样例解释 1

将 $B=(2,1,0,3)$ 初始化后，可以按以下步骤将 $B$ 变为 $A$：

• 选择 $(l,r)=(2,4)$，从 $B$ 中删除 $\mathrm{mex}(\{1,0,3\})=2$，此时 $B=(1,0,3)$。
• 选择 $(l,r)=(3,3)$，从 $B$ 中删除 $\mathrm{mex}(\{3\})=0$，此时 $B=(1,3)$。
  因此，$P=(2,1,0,3)$ 满足条件。满足条件的 $P$ 一共有 $8$ 种，因此输出 $8$。

样例解释 2

只有 $P=(0,3,2,1)$ 满足条件。

样例解释 4

请输出答案对 $998244353$ 取模后的结果。

由 ChatGPT 4.1 翻译