CF1081C Colorful Bricks

在空闲时间，Chouti 喜欢做些家务。他最近有了一个新任务，要在院子里给一些砖块上色。 地上有 $n$ 块砖排成一排。Chouti 手头有 $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$ 取模后的结果。

在第一个样例中，由于 $k=0$，所以每块砖的颜色都必须相同，因此一共有 $m=3$ 种上色方法。 在第二个样例中，假设两种颜色分别为黄色和青柠色，下图展示了所有 $4$ 种可能的上色方式。  由 ChatGPT 4.1 翻译