3405. Count the Number of Arrays with K Matching Adjacent Elements

You are given three integers n, m, k. A good array arr of size n is defined as follows: - Each element in arr is in the inclusive range [1, m]. - Exactly k indices i (where 1 <= i < n) satisfy the condition arr[i - 1] == arr[i]. Return the number of good arrays that can be formed. Since the answer may be very large, return it modulo 109 + 7. Example 1: Input: n = 3, m = 2, k = 1 Output: 4