在空闲时间,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$$$ 可能的颜色。