count-the-number-of-arrays-with-k-matching-adjacent-elements

给你三个整数 n ，m ，k 。长度为 n 的 好数组 arr 定义如下：

• arr 中每个元素都在 闭 区间 [1, m] 中。


• 恰好 有 k 个下标 i （其中 1 <= i < n）满足 arr[i - 1] == arr[i] 。

请你返回可以构造出的 好数组 数目。

由于答案可能会很大，请你将它对 109 + 7 取余 后返回。

示例 1：

输入：n = 3, m = 2, k = 1

输出：4

解释：

• 总共有 4 个好数组，分别是 [1, 1, 2] ，[1, 2, 2] ，[2, 1, 1] 和 [2, 2, 1] 。


• 所以答案为 4 。

示例 2：

输入：n = 4, m = 2, k = 2

输出：6

解释：

• 好数组包括 [1, 1, 1, 2] ，[1, 1, 2, 2] ，[1, 2, 2, 2] ，[2, 1, 1, 1] ，[2, 2, 1, 1] 和 [2, 2, 2, 1] 。


• 所以答案为 6 。

示例 3：

输入：n = 5, m = 2, k = 0

输出：2

解释：

• 好数组包括 [1, 2, 1, 2, 1] 和 [2, 1, 2, 1, 2] 。


• 所以答案为 2 。

提示：

• 1 <= n <= 105


• 1 <= m <= 105


• 0 <= k <= n - 1