A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7). For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd po

countGoodNumbers.js

/**
 * @param {number} n
 * @return {number}
 */
// Define the modulo value to prevent overflow in calculations
const MOD = 1_000_000_007;

function modPow(base, exp, mod) {
    let result = 1n; // Initialize result as 1
    let b = BigInt(base), e = BigInt(exp), m = BigInt(mod); // Convert to BigInt for large numbers
    while (e > 0) {
        // If the current exponent is odd, multiply result by base
        if (e % 2n === 1n) result = (result * b) % m;
        // Square the base and reduce the exponent by half
        b = (b * b) % m;
        e = e / 2n;
    }
    return result;
};

var countGoodNumbers = function(n) {
    // Calculate the number of even and odd positions
    const evenCount = Math.ceil(n / 2); // Number of even positions
    const oddCount = Math.floor(n / 2); // Number of odd positions

    // Calculate the number of ways to fill even and odd positions
    const evenWays = modPow(5, evenCount, MOD); // 5 choices for each even position
    const oddWays = modPow(4, oddCount, MOD); // $ choices for each odd position

    // Multiply results and return modulo MOD
    return Number((evenWays * oddWays) % BigInt(MOD));
};