社交距离 2

题目描述

有 $N$ 把椅子排成一排,称为 1 号椅子、2 号椅子、……、$N$ 号椅子。

一把椅子只能坐一个人。

将有 $M$ 个人分别坐在其中的 $M$ 把椅子上。这里,按如下方式定义得分:

$\displaystyle \prod_{i=1}^{M-1} (B_{i+1} - B_i)$,其中 $B=(B_1,B_2,\ldots,B_M)$ 是这些人所坐椅子的编号按升序排列得到的列表。

第 $i$ 个人($1 \le i \le K$)已经坐在椅子 $A_i$ 上。

其余的 $M-K$ 个人就座的方式共有 $_{N-K} \mathrm{P} _{M-K}$ 种。求所有这些就座方式的得分之和。

由于这个和可能非常大,请输出它对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $K$
$A_1$ $A_2$ $\ldots$ $A_K$

若 $K = 0$,则第二行为空行。

输出格式

输出答案。

样例

5 3 2
1 3

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$。

6 6 1
4

120

每种就座方式的得分都是 $1$。

就座方式共有 $_{5} \mathrm{P} _{5} = 120$ 种,所以答案是 $120$。

99 10 3
10 50 90

761621047

数据范围

• $2 \le N \le 2 \times 10^5$
• $2 \le M \le N$
• $0 \le K \le M$
• $1 \le A_1 \lt A_2 \lt \ldots \lt A_K \le N$
• 输入中的所有值均为整数。