← 返回题目列表

AtCoder · abc253_e

H. 距离序列

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有多少个整数序列 A=(A_1,\ldots,A_N) 长度 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.