/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 列に椅子が N 個並んでおり、椅子 1 、椅子 2 、\ldots 、椅子 N と名前がついています。
1 つの椅子に 2 人以上が座ることはできません。
M 人が椅子に座りますが、座り方によって以下の式で与えられるスコアが定められます。
人が座っている椅子の番号を昇順にソートした数列を B=(B_1,B_2,\ldots,B_M) として、
\displaystyle \prod_{i=1}^{M-1} (B_{i+1} - B_i)
人 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
Score : 600 points
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