#P13646. [ARC160D] Mahjong

    ID: 12848 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-双射计数普通生成函数生成函数求系数容斥原理插板法阶乘逆元预处理

[ARC160D] Mahjong

题目描述

找到可以通过以下两种操作,使得长度为 NN、元素之和为 MM 的数列 AA 全为 00 的 AA 的个数,再取模 998244353998244353。

  1. 在 AA 中选一个元素,将其减去 KK。
  2. 在 AA 中选取长度为 KK 的子串,子串中每个元素减去 11。

输入格式

输入一行整数,分别代表 N M KN~M~K。

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 2 2

输出 #1

5

输入输出样例 #2

输入 #2

100 998244353 100

输出 #2

0

输入输出样例 #3

输入 #3

2000 545782618661124208 533

输出 #3

908877889

说明/提示

  • 1≤K≤N≤20001\le K\le N\le2000
  • 1≤M≤10181\le M\le10^{18}