题目背景

あなたは先へ進み、黒いローブを着た老人に出会った。そこにある門の前には巨大な砂盤が置かれており、老人は手に持った木の枝で砂盤の上に奇妙な記号を描いている。

老人はあなたに、若い頃からある問題に夢中になっていたが、老いさらばえた今でもその答えのほんの一部しか解き明かせていないと語った。

「おそらく、これらを君たちに託すべきなのだろう」と老人は言った。

「あまり心配することはない。君を困らせるつもりはない。少なくとも、必要な道具は用意しておいたから」

問題文

正整数 $\alpha$ に対して、長さ $\alpha n$ の以下の数列 $a$ を考える。

• 各 $k=1,\dots, n$ について、数列 $a$ には $k$ がちょうど $\alpha$ 個含まれる。
• $a_i = a_j$ を満たす $i < j$ に対して、任意の $i < k < j$ について $a_k \geq a_i$ が成り立つ。

上記の条件を満たす数列を $(n,\alpha)$ 次順列と呼ぶ。

今、$(n_0,\alpha)$ 次順列 $P$ が与えられる。また、$n$ と $m$ が与えられるとき、部分列として $P$ を含み、かつ以下の条件を満たす $(n,\alpha)$ 次順列の個数を求めよ。

• $a_i > a_{i+1}$ を満たす添字 $i$ が合計で $m$ 個存在する。

このような数列の総数を $998244353$ で割った余りを求めよ。

入力

第一行に4つの整数 $\alpha, n, m, n_0$ が入力される。

第二行に $\alpha n_0$ 個の正整数が入力される。これらは $(n_0,\alpha)$ 次順列を構成することが保証されている。

出力

条件を満たす数列の個数を整数で出力せよ。

入出力例

入力 1

1 4 2 2
2 1

出力 1

7

入力 2

2 4 2 2
1 2 2 1

出力 2

19

小課題

$10\%$ のデータにおいて、$n \leq 2000$ を満たす。

別の $10\%$ のデータにおいて、$\alpha = 1, n_0=1$ を満たす。

別の $30\%$ のデータにおいて、$\alpha = 1$ を満たす。

別の $15\%$ のデータにおいて、$\alpha = 2, n_0=1$ を満たす。

別の $15\%$ のデータにおいて、$\alpha = 2$ を満たす。

$100\%$ のデータにおいて、$1\leq n \leq 2\times 10^5, 0\leq m < n, 1\leq n_0\leq n, 1\leq \alpha n_0 \leq 2\times 10^5$ を満たす。

注記

形式的べき級数の演算を処理しやすくするため、テンプレートを提供する。必要に応じて参照・使用してもよいし、使用しなくてもよい。