102534: [AtCoder]ABC253 E - Distance Sequence

Problem Statement

How many integer sequences $A=(A_1,\ldots,A_N)$ of length $N$ satisfy all the conditions below?

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

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

Since the count can be enormous, find it modulo $998244353$.

Constraints

• $2 \leq N \leq 1000$
• $1 \leq M \leq 5000$
• $0 \leq K \leq M-1$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $K$

Output

Print the count modulo $998244353$.

Sample Input 1

2 3 1

Sample Output 1

6

The following $6$ sequences satisfy the conditions.

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

Sample Input 2

3 3 2

Sample Output 2

2

The following $2$ sequences satisfy the conditions.

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

Sample Input 3

100 1000 500

Sample Output 3

657064711

Print the count modulo $998244353$.

问题描述

有多少长度为$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$的结果。