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 goo

countGoodArrays.js

/**
 * @param {number} n
 * @param {number} m
 * @param {number} k
 * @return {number}
 */
var countGoodArrays = function(n, m, k) {
    const MOD = 1e9 + 7; // Large prime number for modulo operations to prevent overflow

    // Function to compute (a^b) % MOD using binary exponentiation (efficient power calculation)
    const modPow = (a, b) => {
        let res = 1n, base = BigInt(a);
        b = BigInt(b);
        while (b > 0) {
            if (b % 2n === 1n) // If the current exponent bit is set, multiply result
                res = (res * base) % BigInt(MOD);
            base = (base * base) % BigInt(MOD); // Square the base
            b >>= 1n; // Divide exponent by 2 (shift right)
        }
        return res;
    };

    // Function to compute modular inverse using Fermat’s little theorem: x^(MOD-2) % MOD
    const modInv = (x) => modPow(x, MOD - 2);

    // Compute factorials modulo MOD (for combinatorial calculations)
    let fact = Array(n).fill(1n);
    for (let i = 1; i < n; i++) {
        fact[i] = (fact[i - 1] * BigInt(i)) % BigInt(MOD);
    }

    // Calculate the number of ways to arrange n elements with exactly k adjacent duplicates
    const comb = (fact[n - 1] * modInv(fact[k]) % BigInt(MOD)) * modInv(fact[n - 1 - k]) % BigInt(MOD);

    // Compute the final result using combinatorial properties
    const result = comb * BigInt(m) % BigInt(MOD) * modPow(m - 1, n - 1 - k) % BigInt(MOD);

    return Number(result); // Convert BigInt result back to a regular number for output
};