← 返回题目列表

Codeforces · 1081/C

C. 彩色砖块

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

在空闲时间,Couti 喜欢做一些家务。他接到了一项新任务,在院子里粉刷一些砖块。

地上有 $$$n$$$ 砖块排成一排。 Couti 手头有 $$$m$$$ 不同颜色的油漆桶,因此他将每块砖都涂成 $$$m$$$ 颜色中的一种。

完成所有砖块的涂漆后,Chouti 很满意。他退后一步,决定用这些积木找点乐子。经过数了一下,他发现有 $$$k$$$ 块砖块的颜色与其左边的砖块颜色不同(当然,第一块砖块没有被计算在内)。

所以像往常一样,他需要你的帮助来计算他可以用多少种方式来绘制砖块。如果至少有一块砖以两种方式涂成不同的颜色,则两种涂砖方式是不同的。因为答案可能相当大,所以您只需输出对 $$$998\,244\,353$$$ 取模的路数。

输入

第一行也是唯一一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n,m \leq 2000, 0 \leq k \leq n-1$$$) — 砖块数量、颜色数量和砖块数量,使其颜色与其左侧砖块的颜色不同。

输出

打印一个整数——以$$$998\,244\,353$$$为模对砖块着色的方法数量。

示例

输入 #1

3 3 0

输出 #1

3

输入 #2

3 2 1

输出 #2

4

注意

在第一个示例中,由于$$$k=0$$$,每块砖的颜色应该相同,因此恰好有$$$m=3$$$ 的方法来给砖块着色。

在第二个示例中,假设桶中的两种颜色是黄色和石灰,下图显示了所有 $$$4$$$ 可能的颜色。