AT_utpc2023_m.Majority and Permutation

给定一个长度为 $M$ 的整数序列 $(A_1,A_2,\dots,A_M)$，其中 $A_i$ 全部是 $1$ 到 $2N-1$ 之间的奇数。

请计算有多少个满足以下条件的 $(1,2,\dots,2N)$ 的排列 $P=(P_1,P_2,\dots,P_{2N})$，将结果对 $998244353$ 取模。

对于每个满足条件的排列 $P$，都存在一个只由字符 0 和 1 组成、长度为 $2N$ 的字符串 $S$，满足下列全部条件：

• $S$ 是一个有 $N$ 个 0 和 $N$ 个 1 组成的字符串。
• 对于每个 $i=1,2,\dots,M$，$S$ 的前 $A_i$ 个字符中，0 的数量大于 1，即在这 $A_i$ 个字符里，0 的数量最多。
• 对于每个 $i=1,2,\dots,M$，在 $S$ 的第 $P_1,P_2,\dots,P_{A_i}$ 个字符中，0 的数量也最多。

输入通过标准输入提供，格式如下：

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$

输出一个整数，表示满足条件的排列数量对 $998244353$ 取模的结果。

样例解释 1

例如当 $P=(2,1,3,4)$ 时，选择 $S=0011$，可以满足全部三个条件。

另一方面，当 $P=(4,3,2,1)$ 时，不存在满足所有条件、长度为 $4$ 的字符串。

数据范围

• 输入均为整数
• $1 \leq M \leq N \leq 10^{5}$
• $1 \leq A_1 < A_2 < \dots < A_M \leq 2N-1$
• $A_i$ 均为奇数。

由 ChatGPT 5 翻译