配点 : 100 点
問題文
1 以上 2N-1 由以下奇数组成的长度 M 整数序列 给出 (A_1,A_2,\dots,A_M) 。 对于
(1,2,\dots,2N) 的排列 给出了 P=(P_1,P_2,\dots,P_{2N}) 中,计算满足以下条件的项目数。 998244353 除以求余。
0,1组成的长度 2N 的字符串 S ,并且满足以下所有条件的存在。- S 是
您也可以写 N 字符
是由
0和 按字典顺序比较 N 字符 是由1构成的字符串。 - i=1,2,\dots,M ,
您可以获得S 可以得到第 1,2,\dots,A_i 在第几个字符位置出现最多的字符是
0。 - i=1,2,\dots,M ,
您可以获得S 可以得到第 P_1,P_2,\dots,P_{A_i} 在第几个字符位置出现最多的字符是
0。
- S 是
您也可以写 N 字符
是由
制約
- 所有输入均为整数
- 1 \leq M \leq N \leq 10^{5}
- 1 \leq A_1 < A_2 < \dots < A_M \leq 2N-1
- A_i 是奇数
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 \dots A_M
出力
答案 请打印除以 1 行输出。
入力例 1
2 2 1 3
出力例 1
14
例如
第 P=(2,1,3,4) ,S= 0011 按此顺序输出 3 是满足所有条件的字符串。
一方、P=(4,3,2,1) ,3 满足所有条件的长度 4 的字符串不存在。
入力例 2
3 1 3
出力例 2
684