题目描述

有多少个长度为 $N$ 的整数序列 $A=(A_1,\\ldots,A_N)$ 满足以下所有条件?

• $1\\le A_i \\le M$ $(1 \\le i \\le N)$

• $|A_i - A_{i+1}| \\geq K$ $(1 \\le i \\le N - 1)$

由于计数可能非常大，所以要对 $998244353$ 取模。

约束条件

• $2 \leq N \leq 1000$
• $1 \leq M \leq 5000$
• $0 \leq K \leq M-1$
• 输入中的所有值都是整数。

输入格式

输入以标准输入形式给出，格式如下：

$N$ $M$ $K$

输出格式

输出对 $998244353$ 取模后的计数。

示例输入 1

2 3 1

示例输出 1

6

以下 $6$ 个序列满足条件。

• $(1,2)$
• $(1,3)$
• $(2,1)$
• $(2,3)$
• $(3,1)$
• $(3,2)$

示例输入 2

3 3 2

示例输出 2

2

以下 $2$ 个序列满足条件。

• $(1,3,1)$
• $(3,1,3)$

示例输入 3

100 1000 500

示例输出 3

657064711

输出对 $998244353$ 取模后的计数。