對於一個長度為 $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}$。