分数: 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.