给定三个整数 n、m 和 k 。考虑使用下图描述的算法找出正整数数组中最大的元素。
请你构建一个具有以下属性的数组 arr ：
arr 中包含确切的 n 个整数。1 <= arr[i] <= m 其中 (0 <= i < n) 。arr 之后，search_cost 的值等于 k 。返回在满足上述条件的情况下构建数组 arr 的 方法数量 ，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。
示例 1：
输入：n = 2, m = 3, k = 1 输出：6 解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
示例 2：
输入：n = 5, m = 2, k = 3 输出：0 解释：没有数组可以满足上述条件
示例 3：
输入：n = 9, m = 1, k = 1 输出：1 解释：唯一可能的数组是 [1, 1, 1, 1, 1, 1, 1, 1, 1]
提示：
1 <= n <= 501 <= m <= 1000 <= k <= n