#3405
Count the Number of Arrays with K Matching Adjacent Elements
hard · 58.4% accepted · 429 likes · top 55%
Description
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.
Solution