题目描述

There are $N$ blocks arranged in a row. Let us paint these blocks.

We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.

Find the number of ways to paint the blocks under the following conditions:

• For each block, use one of the $M$ colors, Color $1$ through Color $M$, to paint it. It is not mandatory to use all the colors.
• There may be at most $K$ pairs of adjacent blocks that are painted in the same color.

Since the count may be enormous, print it mod $998244353$.

有 $N$ 块排成一行。让我们给这些积木涂色。

我们将考虑两种涂色方法，当且仅当有一个积木块在这两种涂色方法中被涂成不同的颜色时，它们才是不同的。

求在下列条件下涂色的方法的个数：

• 对于每个图块，从颜色 $1$ 到颜色 $M$ 的 $M$ 种颜色中选择一种进行涂色。并非必须使用所有颜色。
• 最多可以有 $K$ 对相邻的图块使用相同的颜色。

由于计数可能非常庞大，因此请打印出 $998244353$ 的模数。

输入格式

输入内容按以下格式标准输入：

$N$ $M$ $K$

输出格式

打印答案。

样例 #1

样例输入 #1

3 2 1

样例输出 #1

6

样例 #2

样例输入 #2

100 100 0

样例输出 #2

73074801

样例 #3

样例输入 #3

60522 114575 7559

样例输出 #3

479519525

说明

数据规模与约定

• 输入值均为整数
• $1 \leq N, M \leq 2 \times 10^5$
• $0 \leq K \leq N - 1$

样例 $1$ 解释

下列绘制图块的方法满足条件：112"、"121"、"122"、"211"、"212 "和 "221"。这里，数字代表积木的颜色。