P15740 [JAG 2024 Summer Camp #2] Linear Time Inversion Number

给定一个长度为 $N$ 的排列 $\boldsymbol{P}$，Alice 使用逆序数来衡量 $\boldsymbol{P}$ 与排列 $(1, 2, \ldots, N)$ 的接近程度，而 Bob 则使用度量 $\frac{1}{2} \sum_{i=1}^{N} |P_i - i|$。 这里，逆序数是指满足 $i < j$ 且 $P_i > P_j$ 的 $(i, j)$ 对的数量。 给定一个长度为 $K$ 的序列 $\boldsymbol{A} = (A_1, A_2, \ldots, A_K)$，存在 $(N - K)!$ 个长度为 $N$ 的排列以 $\boldsymbol{A}$ 作为其前缀。 找出这些排列中，Alice 的度量与 Bob 的度量相等的排列数量，并将结果对 $998,244,353$ 取模后返回。

输入以如下格式给出： $$ \begin{aligned} &N \ K \\ &A_1 \ A_2 \ \ldots \ A_K \end{aligned} $$ - $1 \leq N \leq 200,000$ - $0 \leq K \leq N$ - $1 \leq A_i \leq N \quad (1 \leq i \leq K)$ - $A_i \neq A_j \quad (i \neq j)$ - 所有输入值均为整数。

输出答案。

翻译由 DeepSeek V3.2 完成