시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB62242338.333%

문제

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