题目描述

正整数 $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$ に対して $A_{(k+j)\bmod\ N}$ を $x_j$ に置き換える．

$1$ 以上 $N$ 以下の整数からなる順列 $B\ =\ (B_0,\ \ldots,\ B_{N-1})$ が与えられます．正整数列 $A$ であって，上記の操作を行った結果が $B$ と一致するものの個数を $998244353$ で割った余りを答えてください．

输入格式

入力は以下の形式で標準入力から与えられます．

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

输出格式

正整数列 $A$ であって，操作を行った結果が $B$ と一致するものの個数を $998244353$ で割った余りを出力してください．

题目大意

题目描述

给定正整数 $N,M,K$。考虑对某个正整数数列 $A=(A_0,\dots,A_{N-1})$ 做如下操作：

• 对所有 $k=0,1,\dots,K-1$ 依次做一遍如下操作：
  • 将 $A_{k\bmod N},A_{(k+1)\bmod N},\dots,A_{(k+M-1)\bmod N}$ 升序排序。

给定一个 $1\sim N$ 间整数的排列 $B=\{B_0,\dots,B_{N-1}\}$。求经过上述操作后与 $B$ 相同的 $A$ 的数量，对 $998244353$ 取模。

样例解释

样例一：

以 $A=(4,1,5,6,2,3)$ 为例，它满足了条件。操作如下：

• $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)$。

样例二：

不存在满足条件的 $A$。

样例三：

所有 $1\sim20$ 间整数的排列都满足条件。

6 3 5
6 4 2 3 1 5

18

6 3 5
6 5 4 3 2 1

0

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

401576539

提示

制約

• $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$

Sample Explanation 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$ に一致する．

Sample Explanation 2

条件を満たす $A$ は存在しません．

Sample Explanation 3

$1$ 以上 $20$ 以下の整数からなる順列がすべて条件を満たします．