题目描述

初始时有一个长度为 $N$ 的全零序列 $A$，你可以执行以下两种操作若干次：

• 选择一个长度为 $K$ 的子区间 $[l:r]$，将区间内所有元素 $+1$。

• 选择一个位置 $1 \leq i \leq n$，将 $A_i$ 修改为 $A_i+K$。

若最终所有元素之和为 $M$，请问可以得到多少种序列 $A$，答案对 $998244353$ 取模。

输入格式

给出三个正整数 $N,M,K$。

输出格式

输出一个整数，表示答案。

输入样例 #1

3 2 2

输出样例 #1

5

输入样例 #2

50 150 3

输出样例 #2

691165258

说明提示

【样例 1 解释】

可以得到 $[2,0,0][0,2,0][0,0,2][1,1,0][0,1,1]$。

输入样例 #3

413 620292 4

输出样例 #3

815419349

数据范围

保证 $M$ 为 $K$ 的倍数。