#P15766. 和式藏色计数

和式藏色计数

题目描述

Mira 在整理一批带数字的筹码。她把正整数 nn 拆成 mm 个正整数的有序和式:

n=a1+a2+⋯+am.n=a_1+a_2+\cdots+a_m.

对一个有序和式 (a1,a2,…,am)(a_1,a_2,\ldots,a_m),定义

f(a1,a2,…,am)f(a_1,a_2,\ldots,a_m)

为这些数 a1,a2,…,ama_1,a_2,\ldots,a_m 中不同整数的个数。

现在需要对所有把 nn 拆成 mm 个正整数的有序和式,求 f(a1,a2,…,am)f(a_1,a_2,\ldots,a_m) 的总和,并对 998244353998244353 取模输出。

两个有序和式

a1+a2+⋯+am=na_1+a_2+\cdots+a_m=n

和

b1+b2+⋯+bm=nb_1+b_2+\cdots+b_m=n

被认为不同,当且仅当存在某个 i∈{1,2,…,m}i\in\{1,2,\ldots,m\},使得 ai≠bia_i\ne b_i。

输入格式

输入仅一行,包含两个整数 n,mn,m。

输出格式

输出答案对 998244353998244353 取模后的结果。

数据范围

  • 1≤n≤10181\le n\le 10^{18};
  • 1≤m≤5001\le m\le 500;
  • m≤nm\le n。

样例 1

输入

10 2

输出

17

样例 2

输入

20 4

输出

3413