Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

There are n - 1 boundaries between adjacent elements. Choose exactly k boundaries where the values match. At every other boundary, the next value must differ from the previous one. Once those boundary types are fixed, their choices multiply independently.

Approach

Choose the matching boundaries in C(n - 1, k) ways. Choose the first array value in m ways. A matching boundary forces the next value, while each of the remaining n - 1 - k boundaries permits m - 1 choices.

Multiply these factors and return the result modulo 1,000,000,007: C(n - 1, k) * m * (m - 1)^(n - 1 - k). Python computes the binomial coefficient and power as exact integers before the final remainder. JavaScript instead uses modular products, a modular inverse for the binomial denominator, and modular exponentiation. The inverse is valid because n is smaller than the prime modulus.

Each array determines exactly one boundary pattern, so it is counted once. If every boundary matches, the exponent is zero and the answer is m; when m = 1, any required differing boundary makes the answer zero.

class Solution:
    def countGoodArrays(self, n: int, m: int, k: int) -> int:
        MOD = 10**9 + 7
        return comb(n - 1, k) * m * pow(m - 1, n - k - 1) % MOD

Complexity analysis

Let e = n-1-k and c = min(k,e). JavaScript uses O(c + log(e + 2) + log MOD) bounded-size modular arithmetic steps and O(1) auxiliary machine words under the stated bounds. Python's two-argument pow is not modular: it materializes (m-1)^e, as well as the exact binomial coefficient and their product. Let B >= 1 bound these intermediate bit lengths, with B = O(n + e*log(m + 1) + log(m + 1)), hence O(n log(m + 1)) in the worst case. If C(n,c) is the bit cost of math.comb and M(B) the cost of multiplying B-bit integers, a conservative Python time bound is O(C(n,c) + M(B)*log(e + 2) + B). Python needs O(B) live integer bits plus math.comb's workspace, not constant-size modular operands.