题目描述

在遥远的色彩王国里，$N$ 个方块排成一列，等待着被赋予生命。这些方块将被涂上不同的颜色，以展现它们的独特魅力。

两个方块列的涂色方式被认为是不同的，如果至少存在一个方块，它在两个列中被涂上了不同的颜色。

你的任务是计算满足以下条件的方块列涂色方式的总数：

• 每个方块可以被涂上从颜色 $1$ 到颜色 $M$ 的任意一种颜色。不使用的颜色也是允许的。
• 相邻的两个方块中，涂有相同颜色的对数不超过 $K$ 对。

由于答案可能非常大，请输出对 $998244353$ 取模后的结果。

输入格式

第一行包含三个整数 $N,M,K$。

输出格式

输出一个整数满足条件的涂色方式的总数。

样例

3 2 1

6

解释 #1

用颜色编号表示方块列的涂色方式，满足条件的涂色方式有：112 , 121, 122, 211, 212, 221。

100 100 0

73074801

数据范围

• $1\ \leq\ N,\ M\ \leq\ 2\ \times\ 10^5$
• $0\ \leq\ K\ \leq\ N\ -\ 1$