题目描述

有 $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