题目描述

找到满足以下条件的 $N$ 个非负整数序列 $A=(A_1,A_2,\\dots,A_N)$ 总数对 $998244353$ 取模。

• 通过反复选择以下操作之一并执行，可以使得 $A$ 的所有元素都变为 $0$。
  • 选择一个整数 $i$ 满足 $1 \\le i \\le N$，将 $A_i$ 减少 $K$。
  • 选择一个整数 $i$ 满足 $1 \\le i \\le N-K+1$，将 $A_i,A_{i+1},\\dots,A_{i+K-1}$ 每个减少 $1$。

约束条件

• $1 \\le K \\le N \\le 2000$
• $1 \\le M \\le 10^{18}$

输入

输入以以下格式从标准输入给出：

$N$ $M$ $K$

输出

输出答案。

示例输入 1

3 2 2

示例输出 1

5

以下五种序列满足要求。

• $(1,1,0)$
• $(0,1,1)$
• $(2,0,0)$
• $(0,2,0)$
• $(0,0,2)$

例如，如果 $A=(0,1,1)$，你可以执行以下操作使得 $A$ 的所有元素都变为 $0$。

• 执行第二个操作。选择 $i = 2$，将 $A_2$ 和 $A_3$ 各减少 $1$，得到 $A=(0,0,0)$。

示例输入 2

100 998244353 100

示例输出 2

0

可能没有满足条件的序列。

示例输入 3

2000 545782618661124208 533

示例输出 3

908877889