分数: 700 点
问题陈述
求模数 998244353,序列 N 非负整数 A=(A_1,A_2,\dots,A_N) 总计 M 满足以下条件。
- 可以使所有元素 A 等于 0 通过重复选择以下操作之一并执行它。
- 选择一个整数 i 这样 1 \le i \le N 并减少 A_i by K.
- 选择一个整数 i 这样 1 \le i \le N-K+1 并减少每个 A_i,A_{i+1},\dots,A_{i+K-1} by 1.
约束
- 1 \le K \le N \le 2000
- 1 \le M \le 10^{18}
输入
输入由标准输入按以下格式给出:
N M K
输出
打印答案。
示例输入 1
3 2 2
示例输出 1
5
以下五个序列满足要求。
- (1,1,0)
- (0,1,1)
- (2,0,0)
- (0,2,0)
- (0,0,2)
例如,如果 A=(0,1,1),您可以执行以下操作来使所有元素 A 等于 0.
- 执行第二个操作。选择 i = 2 减少每个 A_2 和 A_3 by 1, 制作 A=(0,0,0).
示例输入 2
100 998244353 100
示例输出 2
0
可能没有满足要求的序列。
示例输入 3
2000 545782618661124208 533
示例输出 3
908877889