Count the Number of Arrays with K Matching Adjacent Elements
You are given three integers n, m, and k. A good array arr of size n is defined as follows:
- Each element in
arris in the inclusive range[1, m]. - Exactly
kindicesi, where1 <= i < n, satisfy the conditionarr[i - 1] == arr[i].
Return the number of good arrays that can be formed.
Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input
n = 3, m = 2, k = 1Output
4There are 4 good arrays: [1, 1, 2], [1, 2, 2], [2, 1, 1], and [2, 2, 1].
Example 2
Input
n = 4, m = 2, k = 2Output
6There are 6 good arrays: [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 1, 1, 1], [2, 2, 1, 1], and [2, 2, 2, 1].
Constraints
- 1 <= n <= 10^5
- 1 <= m <= 10^5
- 0 <= k <= n - 1