题目描述

给定正整数 $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+j)\bmod N}$ 替换为 $x_j$，其中 $0\leq j < M$，$(x_0, \ldots, x_{M-1})$ 为将 $A_{k\bmod N}, A_{(k+1)\bmod N}, \ldots, A_{(k+M-1)\bmod N}$ 按升序排序的结果。

给定一个从 $1$ 到 $N$ 的排列 $B = (B_0, \ldots, B_{N-1})$。求在执行上述操作后，与 $B$ 相等的正整数序列 $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$。

输入

从标准输入读入数据，输入格式如下：

$N$ $M$ $K$ $B_0$ $\ldots$ $B_{N-1}$

输出

输出正整数序列 $A$ 的数量，使得执行操作后与 $B$ 相等，并对 $998244353$ 取模。

示例输入 1

6 3 5
6 4 2 3 1 5

示例输出 1

18

例如，$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

6 3 5
6 5 4 3 2 1

示例输出 2

0

没有序列 $A$ 满足条件。

示例输入 3

20 20 149
13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12

示例输出 3

401576539

从 $1$ 到 $20$ 的所有排列都满足条件。