102257: [AtCoder]ABC225 H - Social Distance 2

Problem Statement

There are $N$ chairs arranged in a row, called Chair $1$, Chair $2$, $\ldots$, Chair $N$.
A chair seats only one person.

$M$ people will sit on $M$ of these chairs. Here, let us define the score as follows:

$\displaystyle \prod_{i=1}^{M-1} (B_{i+1} - B_i)$, where $B=(B_1,B_2,\ldots,B_M)$ is the sorted list of the indices of the chairs the people sit on.

Person $i$ $(1 \leq i \leq K)$ is already sitting on Chair $A_i$.
There are ${} _ {N-K} \mathrm{P} _ {M-K}$ ways for the other $M-K$ people to take seats. Find the sum of the scores for all of these ways.

Since this sum may be enormous, compute it modulo $998244353$.

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

5 3 2
1 3

Sample Output 1

7

If Person $3$ sits on Chair $2$, the score will be $(2-1) \times (3-2)=1 \times 1 = 1$.
If Person $3$ sits on Chair $4$, the score will be $(3-1) \times (4-3)=2 \times 1 = 2$.
If Person $3$ sits on Chair $5$, the score will be $(3-1) \times (5-3)=2 \times 2 = 4$.
The answer is $1+2+4=7$.

Sample Input 2

6 6 1
4

Sample Output 2

120

The score for every way of sitting will be $1$.
There are ${} _ {5} \mathrm{P} _ {5} = 120$ ways of sitting, so the answer is $120$.

Sample Input 3

99 10 3
10 50 90

Sample Output 3

761621047

问题描述

有一排$N$把椅子，分别叫做椅子$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$上。

其余$M-K$个人有${} _ {N-K} \mathrm{P} _ {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