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$

输出

输出答案。

3 2 1

6

以下给方块上色的方案满足条件：112、121、122、211、212 和 221。这里，数字表示方块的颜色。

100 100 0

73074801

60522 114575 7559

479519525