길이가 $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$가 있습니다(중복 가능). Little 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}$입니다.