AT_arc149_e [ARC149E] Sliding Window Sort

[problemUrl]: https://atcoder.jp/contests/arc149/tasks/arc149_e 正整数 $ 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\

入力は以下の形式で標準入力から与えられます． > $ N $ $ M $ $ K $ $ 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 $ ### 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 $ 以下の整数からなる順列がすべて条件を満たします．