目标
给你三个整数 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 <= 10^5
- 1 <= m <= 10^5
- 0 <= k <= n - 1
思路
//todo
代码