分数: 600 点
问题陈述
有 N 椅子排成一排,称为Chair 1,椅子 2, \ldots,椅子 N.
一把椅子只能容纳一个人。
M 人们会坐在 这些椅子的 M 。在这里,我们将分数定义如下:
\displaystyle \prod_{i=1}^{M-1} (B_{i+1} - B_i),其中 B=(B_1,B_2,\ldots,B_M) 是人们所坐椅子索引的排序列表。
人 i (1 \leq i \leq K) 已经坐在椅子上 A_i.
有 {} _ {N-K} \mathrm{P} _ {M-K} 其他方法 M-K 人们入座。求所有这些方式的分数总和。
由于这个总和可能很大,所以计算它的模 998244353.
约束
- 2 \leq N \leq 2 \times 10^5
- 2 \leq M \leq N
- 0 \leq K \leq M
- 1 \leq A_1 \lt A_2 \lt \ldots \lt A_K \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M K A_1 A_2 \ldots A_K
输出
打印答案。
示例输入 1
5 3 2 1 3
示例输出 1
7
如果人 3 坐在椅子上 2,分数将为 (2-1) \times (3-2)=1 \times 1 = 1.
如果人 3 坐在椅子上 4,分数将为 (3-1) \times (4-3)=2 \times 1 = 2.
如果人 3 坐在椅子上 5,分数将为 (3-1) \times (5-3)=2 \times 2 = 4.
答案是 1+2+4=7.
示例输入 2
6 6 1 4
示例输出 2
120
每种坐姿的得分将为 1.
有 {} _ {5} \mathrm{P} _ {5} = 120 坐姿,所以答案是 120.
示例输入 3
99 10 3 10 50 90
示例输出 3
761621047