AT_arc149_e [ARC149E] Sliding Window Sort

给定正整数 $N$、$M$、$K$。考虑对正整数序列 $A = (A_0, \ldots, A_{N-1})$ 进行如下操作： - 按照 $k = 0, 1, \ldots, K-1$ 的顺序，依次进行以下操作： - 将 $A_{k\bmod N},\ A_{(k+1)\bmod N},\ \ldots,\ A_{(k+M-1)\bmod N}$ 升序排序。也就是说，将 $A_{k\bmod N},\ A_{(k+1)\bmod N},\ \ldots,\ A_{(k+M-1)\bmod N}$ 按从小到大排列为 $(x_0, \ldots, x_{M-1})$ 时，对于每个 $0 \leq j < M$，用 $x_j$ 替换 $A_{(k+j)\bmod N}$。 给定一个由 $1$ 到 $N$ 之间的整数构成的排列 $B = (B_0, \ldots, B_{N-1})$。请你计算有多少个正整数序列 $A$，使得经过上述操作后，$A$ 恰好变为 $B$。请将答案对 $998244353$ 取模后输出。

输入以如下格式从标准输入读入： > $N$ $M$ $K$ $B_0$ $B_1$ $\ldots$ $B_{N-1}$

输出满足条件的正整数序列 $A$ 的个数，对 $998244353$ 取模后的结果。

## 限制条件 - $2 \leq N \leq 3 \times 10^5$ - $2 \leq M \leq N$ - $1 \leq K \leq 10^9$ - $1 \leq B_i \leq N$ - 如果 $i \neq j$，则 $B_i \neq B_j$ ## 样例解释 1 例如 $A = (4,1,5,6,2,3)$ 满足条件。对于该 $A$，操作过程如下： - $k=0$ 时，$A$ 变为 $(1,4,5,6,2,3)$。 - $k=1$ 时，$A$ 变为 $(1,4,5,6,2,3)$。 - $k=2$ 时，$A$ 变为 $(1,4,2,5,6,3)$。 - $k=3$ 时，$A$ 变为 $(1,4,2,3,5,6)$。 - $k=4$ 时，$A$ 变为 $(6,4,2,3,1,5)$，与 $B$ 一致。 ## 样例解释 2 不存在满足条件的 $A$。 ## 样例解释 3 所有由 $1$ 到 $20$ 组成的排列都满足条件。 由 ChatGPT 4.1 翻译