You are given an array nums of n positive integers and an integer k. Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times: Choose any non-empty subarray nums[l, ..., r] that you

maximumScore.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// A class to handle modular arithmetic operations
class Modulo {
    constructor(modulo) {
        this.modulo = modulo; // The modulus for all operations
        this._phi = modulo - 1; // Euler's totient function for primes (modulo is prime)
    }

    // Get the precomputed value of Euler's totient function
    getPhi() {
        return this._phi;
    }

    // Compute the modular inverse of 'a' under the current modulus
    getInverse(a) {
        return this.pow(a, this.getPhi() - 1); // Using Fermat's little theorem
    }

    // Add multiple numbers under the modulus
    add(...numbers) {
        let result = 0;
        for (let number of numbers) {
            result = (result + (number % this.modulo)) % this.modulo; // Add numbers modulo
        }
        if (result < 0) result += this.modulo; // Handle negative results
        return result;
    }

    // Efficiently compute (a * b) % modulo using repeated addition
    _quickMul(a, b) {
        a = ((a % this.modulo) + this.modulo) % this.modulo; // Normalize 'a'
        b = ((b % this.modulo) + this.modulo) % this.modulo; // Normalize 'b'
        if (a === 0 || b === 0) return 0; // Multiplication with zero
        let result = 0;
        while (b) {
            while (b % 2 === 0) { // When 'b' is even, double 'a' and halve 'b'
                a = (a * 2) % this.modulo;
                b /= 2;
            }
            if (b % 2 !== 0) { // Add 'a' to the result if 'b' is odd
                result = (result + a) % this.modulo;
                b--;
            }
        }
        return result;
    }

    // Multiply multiple numbers under the modulus
    mul(...numbers) {
        let result = 1;
        for (let number of numbers) {
            if (number > 0 && number < 1) // Handle fractions by computing modular inverse
                number = this.getInverse(Math.round(1 / number));
            result = this._quickMul(result, number); // Multiply with modular arithmetic
            if (result === 0) return 0; // Stop early if result is zero
        }
        if (result < 0) result += this.modulo; // Handle negative results
        return result;
    }

    // Divide 'a' by 'b' under the modulus (a / b % modulo)
    div(a, b) {
        return this._quickMul(a, this.getInverse(b)); // Multiply by modular inverse of 'b'
    }

    // Compute (a^b) % modulo using modular exponentiation
    pow(a, b) {
        a = ((a % this.modulo) + this.modulo) % this.modulo; // Normalize 'a'
        if (a === 0) return 0; // Zero to any power is zero
        let result = 1;
        while (b) {
            while (b % 2 === 0) { // When 'b' is even, square 'a' and halve 'b'
                a = this._quickMul(a, a);
                b /= 2;
            }
            if (b % 2 !== 0) { // Multiply 'result' by 'a' if 'b' is odd
                result = this._quickMul(result, a);
                b--;
            }
        }
        return result;
    }
}

// Initialize modular arithmetic with modulo 1e9+7
const mod = new Modulo(1000000007);

// Initialize the Sieve of Eratosthenes to count prime factors for numbers up to 'n'
function initEratosthenesSieve(n) {
    let eratosthenesSieve = Array(n + 1).fill(0); // Array to store counts of prime factors
    eratosthenesSieve[1] = 0; // 1 has no prime factors
    for (let i = 2; i <= n; i++) {
        if (!eratosthenesSieve[i]) { // 'i' is prime if its count is still 0
            for (let j = i; j <= n; j += i) { // Increment counts for multiples of 'i'
                eratosthenesSieve[j]++;
            }
        }
    }
    return eratosthenesSieve;
}

// Precompute the prime factor counts for numbers up to 100,000
let eratosthenesSieve = initEratosthenesSieve(100000);

// Function to calculate the maximum score
var maximumScore = function (nums, k) {
    const n = nums.length; // Length of the array
    const pre = Array(n).fill(0); // Array to store previous lower-priority indices
    const pos = Array(n).fill(n); // Array to store next higher-priority indices

    // Helper function to compare priority based on prime factor count
    function isMorePriority(l, r) {
        return eratosthenesSieve[nums[l]] >= eratosthenesSieve[nums[r]];
    }

    let st = []; // Stack for finding previous lower-priority indices
    for (let i = 0; i < n; i++) {
        while (st.length && !isMorePriority(st[st.length - 1], i)) st.pop();
        pre[i] = st.length ? st[st.length - 1] : -1; // Update 'pre' array
        st.push(i);
    }

    st = []; // Stack for finding next higher-priority indices
    for (let i = n - 1; i >= 0; i--) {
        while (st.length && isMorePriority(i, st[st.length - 1])) st.pop();
        pos[i] = st.length ? st[st.length - 1] : n; // Update 'pos' array
        st.push(i);
    }

    // Sort indices by element values in descending order
    const indices = Array.from(Array(n), (_, i) => i);
    indices.sort((a, b) => nums[b] - nums[a]);

    let result = 1; // Initial score
    for (let i = 0; i < n; i++) {
        const ind = indices[i]; // Current index
        const pow = Math.min((ind - pre[ind]) * (pos[ind] - ind), k); // Maximum power usable for this element
        result = mod.mul(result, mod.pow(nums[ind], pow)); // Update result using modular multiplication
        k -= pow; // Decrease remaining operations
        if (!k) return result; // Stop if no operations are left
    }
};