Pour une permutation $p$ de longueur $n$, on définit $f(p)$ comme l'ensemble des positions des maximums de préfixe. Plus précisément, $f(p) = \{i \mid 1 \le i \le n, \text{ s.t. } \forall 1 \le j < i, p_i > p_j\}$.
De même, soit $g(p)$ l'ensemble des valeurs des maximums de préfixe, c'est-à-dire $g(p) = \{p_i \mid i \in f(p)\}$.
On choisit maintenant $k$ permutations $p_1, p_2, \ldots, p_k$ de manière indépendante et uniformément au hasard parmi toutes les permutations de longueur $n$ (avec répétition possible). Little A veut connaître le nombre espéré de $g(p)$ essentiellement différents parmi ces permutations. L'objectif est de déterminer combien d'ensembles essentiellement différents on obtient en espérance parmi $g(p_1), g(p_2), \ldots, g(p_k)$. La réponse doit être affichée modulo $998244353$.
Entrée
Une seule ligne contenant deux entiers $n, k$ ($1 \le n, k \le 5000$).
Sortie
Une seule ligne contenant un entier représentant le résultat de la réponse modulo $998244353$.
Exemples
Entrée 1
1 1
Sortie 1
1
Entrée 2
3 2
Sortie 2
388206139
Entrée 3
3 4
Sortie 3
408232647
Entrée 4
112 646
Sortie 4
928854225
Remarque
Pour le premier exemple, la réponse est $1$.
Pour le deuxième exemple, la réponse est $\frac{31}{18}$.
Pour le troisième exemple, la réponse est $\frac{1711}{648}$.