← 返回题目列表

AtCoder · abc167_e

E. 彩色块

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

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