長さ $n$ の順列 $p$ に対して、累積最大値(prefix maximum)の位置の集合を $f(p)$ と定義します。具体的には、$f(p) = \{i \mid 1 \le i \le n, \text{ s.t. } \forall 1 \le j < i, p_i > p_j\}$ です。
同様に、累積最大値の値の集合を $g(p)$ とします。すなわち、$g(p) = \{p_i \mid i \in f(p)\}$ です。
いま、長さ $n$ のすべての順列から独立かつ一様ランダムに $k$ 個の順列 $p_1, p_2, \ldots, p_k$ を選びます(重複しても構いません)。Little A は、これらの順列の中に本質的に異なる $g(p)$ が期待値としていくつあるかを知りたいです。目標は、$g(p_1), g(p_2), \ldots, g(p_k)$ の中に本質的に異なる集合が期待値としていくつあるかを求めることです。答えを $998244353$ で割った余りを出力してください。
入力
1 行に 2 つの整数 $n, k$ ($1 \le n, k \le 5000$) が与えられます。
出力
答えを $998244353$ で割った余りを表す整数を 1 行に出力してください。
入出力例
入力 1
1 1
出力 1
1
入力 2
3 2
出力 2
388206139
入力 3
3 4
出力 3
408232647
入力 4
112 646
出力 4
928854225
注記
1 つ目の出力例では、答えは $1$ です。
2 つ目の出力例では、答えは $\frac{31}{18}$ です。
3 つ目の出力例では、答えは $\frac{1711}{648}$ です。