题目描述

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

• $1 \leq A_i \leq M$，其中 $1 \leq i \leq N$。
• $|A_i - A_{i+1}| \geq K$，其中 $1 \leq i \leq N-1$。

请注意，答案可能非常大，请输出答案对 $998244353$ 取模后的结果。

输入格式

输入以如下格式从标准输入中给出。

$N$ $M$ $K$

输出格式

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

样例 1

输入

2 3 1

输出

6

样例 2

输入

3 3 2

输出

2

样例 3

输入

100 1000 500

输出

657064711

说明/提示

限制条件

• $2 \leq N \leq 1000$
• $1 \leq M \leq 5000$
• $0 \leq K \leq M-1$
• 输入均为整数

样例解释 1

满足条件的数列如下，共有 $6$ 个。

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

样例解释 2

满足条件的数列如下，共有 $2$ 个。

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

样例解释 3

请输出答案对 $998244353$ 取模后的结果。

由 ChatGPT 4.1 翻译