시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 17 9 9 52.941%

문제

Consider all ordered partitions of a positive integer $n$ into $m$ positive summands: $n = a_1 + a_2 + \ldots + a_m$. Let $f(a_1, a_2, \ldots, a_m)$ be the number of different integers among $a_1, a_2, \ldots, a_m$. Find the sum of $f(a_1, a_2, \ldots, a_m)$ over all ordered partitions of the number $n$, and print it modulo $998\,244\,353$.

Two ordered partitions $a_1 + a_2 + \ldots + a_m = n$ and $b_1 + b_2 + \ldots + b_m = n$ are considered different if there is an index $i \in \{1, 2, \ldots, m\}$ such that $a_i \neq b_i$.

입력

The only line of input contains two integers $n$ and $m$ ($1 \le n \le 10^{18}$, $1 \le m \le 500$, $m \le n$).

출력

Print the answer modulo $998\,244\,353$.

예제 입력 1

10 2

예제 출력 1

17

예제 입력 2

20 4

예제 출력 2

3413