← 返回题目列表

AtCoder · utpc2023_m

M. 多数和排列

中文机器翻译题面 查看原题

配点 : 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 。

制約

  • 所有输入均为整数
  • 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