题目描述

$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$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

有 $N$ 个椅子排列在一行，一个椅子只能坐一个人，$M$ 个人每个人会坐一把椅子，假设 $B_1,...,B_m$ 是他们坐的椅子排序后的序列，那么这样的贡献是 $\prod_{i=1}^{m-1} (b_{i+1}-b_i)$。

现在有 $k$ 个人已经确定了座位，求对于剩下的人的每种可能坐的位置的排列的贡献之和。

• $2\leq N\leq 2\times 10^5,2\leq M\leq N,0\leq K\leq M,1\leq A_1<A_2<...<A_K\leq N$

5 3 2
1 3

7

6 6 1
4

120

99 10 3
10 50 90

761621047

提示

制約

• $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 $
• 入力は全て整数

Sample Explanation 1

人 $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$ です。

Sample Explanation 2

全ての座り方でスコアは $1$ です。 座り方は ${}\ _\ {5}\ \mathrm{P}\ _\ {5}\ =\ 120$ 通りあるので、答えは $120$ です。