← 返回题目列表

AtCoder · abc225_h

H. 社交距离 2

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

分数: 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