問題文

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

制約

• $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$ 以下の整数からなる順列がすべて条件を満たします．