分数: 100 点
问题陈述
给你正整数 N, M, K,以及一系列 K 正整数 c=(c_1, c_2, \dots, c_K).
A 多套 S 组成 N 小于或等于的正整数 M 被称为 好,如果存在至少一个序列 K 多套 (S_1, S_2, \dots, S_K) 满足以下条件。
- 没有一个 S_1, S_2, \dots, S_K 为空。
- 的中位数 S_i 等于 c_i,对于所有 i=1, 2, \dots, K.
- S_1, S_2, \dots, S_K 正好有 总共 N 个元素。由这些组成的多重集 N 元素符合 S.
请注意,我们定义了多重集的中位数 T 与 n\ (\geq 1) 元素作为 \lceil n / 2 \rceil第一个元素 T 按升序排列。例如,中位数为 T=\lbrace 1, 2, 3, 4 \rbrace is 2,以及 T=\lbrace 1, 3, 5, 7, 7 \rbrace is 5.
求模的良好多重集的数量 998244353.
约束
- 1 \leq N, M \leq 10^7
- 1 \leq K \leq \min(2 \times 10^5, N)
- 1 \leq c_i \leq M
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N \ M \ K c_1 \ c_2 \ \dots \ c_K
输出
打印良好的多重集模数 998244353.
示例输入 1
8 5 3 4 1 5
示例输出 1
105
例如, S=\lbrace 1,1,1,2,3,4,5,5 \rbrace 是一个很好的多重集,因为存在 (S_1, S_2, S_3) 满足如下条件。
- S_1 = \lbrace 1, \mathbf{4}, 5 \rbrace
- S_2 = \lbrace 1, \mathbf{1}, 2, 3 \rbrace
- S_3 = \lbrace \mathbf{5} \rbrace
示例输入 2
10000000 2 2 1 2
示例输出 2
9999999
示例输入 3
30 10 5 3 1 4 1 5
示例输出 3
38446044