距离序列

题目描述

求满足以下所有条件的长为 $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$ 取模后的个数。

样例

2 3 1

6

满足条件的序列有以下 6 个：

$(1,2)$

$(1,3)$

$(2,1)$

$(2,3)$

$(3,1)$

$(3,2)$

3 3 2

2

满足条件的序列有以下 2 个：

$(1,3,1)$

$(3,1,3)$

100 1000 500

657064711

数据范围

• $2 \le N \le 1000$
• $1 \le M \le 5000$
• $0 \le K \le M-1$
• 输入中的所有值均为整数。