Dla permutacji $p$ o długości $n$ definiujemy $f(p)$ jako zbiór pozycji maksimów prefiksowych. Dokładniej, $f(p) = \{i \mid 1 \le i \le n, \text{ s.t. } \forall 1 \le j < i, p_i > p_j\}$.
Podobnie niech $g(p)$ oznacza zbiór wartości maksimów prefiksowych, czyli $g(p) = \{p_i \mid i \in f(p)\}$.
Teraz spośród wszystkich permutacji o długości $n$ wybieramy niezależnie i jednostajnie losowo $k$ permutacji $p_1, p_2, \ldots, p_k$ (mogą się powtarzać). Mały A chce wiedzieć, jaka jest wartość oczekiwana liczby istotnie różnych zbiorów $g(p)$ wśród tych permutacji. Celem jest wyznaczenie oczekiwanej liczby istotnie różnych zbiorów wśród $g(p_1), g(p_2), \ldots, g(p_k)$. Odpowiedź należy wypisać modulo $998244353$.
Wejście
Jeden wiersz zawierający dwie liczby całkowite $n, k$ ($1 \le n, k \le 5000$).
Wyjście
Jeden wiersz zawierający jedną liczbę całkowitą oznaczającą wynik odpowiedzi modulo $998244353$.
Przykład
Wejście 1
1 1
Wyjście 1
1
Wejście 2
3 2
Wyjście 2
388206139
Wejście 3
3 4
Wyjście 3
408232647
Wejście 4
112 646
Wyjście 4
928854225
Uwagi
Dla pierwszego przykładu odpowiedź wynosi $1$.
Dla drugiego przykładu odpowiedź wynosi $\frac{31}{18}$.
Dla trzeciego przykładu odpowiedź wynosi $\frac{1711}{648}$.