← 返回题目列表

AtCoder · arc160_d

D. 麻将

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

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