分数: 500 点
问题陈述
有 N 块排列成一行。让我们绘制这些块。
我们将考虑两种方法来对块进行不同的绘制,当且仅当有一个块以这两种方式绘制为不同的颜色时。
找出在以下条件下绘制方块的方法数量:
- 对于每个块,使用其中之一 M 颜色, 颜色 1 通过颜色 M,绘制它。并不强制要求使用所有颜色。
- 最多可能有 K 涂有相同颜色的相邻块对。
由于计数可能很大,因此将其模数打印出来 998244353.
约束
- 输入中的所有值都是整数。
- 1 \leq N, M \leq 2 \times 10^5
- 0 \leq K \leq N - 1
输入
输入由标准输入按以下格式给出:
N M K
输出
打印答案。
示例输入 1
3 2 1
示例输出 1
6
以下绘制方块的方法满足条件: 112, 121, 122, 211, 212,和 221。这里,数字代表块的颜色。
示例输入 2
100 100 0
示例输出 2
73074801
示例输入 3
60522 114575 7559
示例输出 3
479519525