题目描述

長さ $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$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

输出格式

答えを $998244353$ で割った余りを出力せよ。

题目大意

求有多少长度为 $n$ 的数列 $A$，满足以下条件：

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

$2 \leq n \leq 1000$，$1 \leq m \leq 5000$，$0 \leq k \leq m - 1$

2 3 1

6

3 3 2

2

100 1000 500

657064711

提示

制約

• $2\ \leq\ N\ \leq\ 1000$
• $1\ \leq\ M\ \leq\ 5000$
• $0\ \leq\ K\ \leq\ M-1$
• 入力は全て整数

Sample Explanation 1

条件を満たす数列は以下の $6$ つです。 - $(1,2)$ - $(1,3)$ - $(2,1)$ - $(2,3)$ - $(3,1)$ - $(3,2)$

Sample Explanation 2

条件を満たす数列は以下の $2$ つです。 - $(1,3,1)$ - $(3,1,3)$

Sample Explanation 3

答えを $998244353$ で割った余りを出力してください。