配点 : $700$ 点

問題文

正整数 $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$ に置き換える．
• $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$ で割った余りを答えてください．

制約

• $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$ で割った余りを出力してください．

6 3 5
6 4 2 3 1 5

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

6 3 5
6 5 4 3 2 1

0

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

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

401576539

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