[ABC253E] 距离序列

题目描述

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

• $1\le A_i\le M$（$1\le i\le N$）
• $|A_i - A_{i+1}|\ge K$（$1\le i\le N-1$）

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

输入格式

输入通过标准输入按以下形式给出：

$N$ $M$ $K$

输出格式

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

输入输出样例 #1

输入 #1

2 3 1

输出 #1

6

输入输出样例 #2

输入 #2

3 3 2

输出 #2

2

输入输出样例 #3

输入 #3

100 1000 500

输出 #3

657064711

说明/提示

限制条件

• $2\le N\le 1000$
• $1\le M\le 5000$
• $0\le K\le 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$ 取模的结果。