Different Summands Counting

양의 정수 n을 m개의 양의 정수 합으로 나타내는 모든 순서 있는 분할에 대해 서로 다른 값의 개수를 더한 값을 998244353으로 나눈 나머지를 구한다. n은 최대 1e18이다.

어려움8조합론동적 계획법수학아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제

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

Two ordered partitions a_1+a_2++a_m=na\_1 + a\_2 + \ldots + a\_m = n and b_1+b_2++b_m=nb\_1 + b\_2 + \ldots + b\_m = n are considered different if there is an index i1,2,,mi \in \\{1, 2, \ldots, m\\} such that a_ib_ia\_i \neq b\_i.

입력

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

출력

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