對於一個長度為 $n$ 的排列 $p$,我們定義 $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$(可以重複)。小 A 想知道在這些排列中,期望有多少個本質不同的 $g(p)$?目標是求出在 $g(p_1), g(p_2), \ldots, g(p_k)$ 之中,期望有多少個本質不同的集合?答案請對 $998244353$ 取模後輸出。
輸入格式
僅一行,包含兩個整數 $n, k$ ($1 \le n, k \le 5000$)。
輸出格式
僅一行,包含一個整數,表示答案對 $998244353$ 取模後的結果。
範例
輸入格式 1
1 1
輸出格式 1
1
輸入格式 2
3 2
輸出格式 2
388206139
輸入格式 3
3 4
輸出格式 3
408232647
輸入格式 4
112 646
輸出格式 4
928854225
說明
對於第一個範例,答案為 $1$。
對於第二個範例,答案為 $\frac{31}{18}$。
對於第三個範例,答案為 $\frac{1711}{648}$。