Start with a score of 1. In each operation, choose a nonempty contiguous subarray of nums that has not been chosen before. Within that subarray, select the element with the largest prime score, breaking ties by the smallest original index, and multiply your score by that element's value.
An integer's prime score is its number of distinct prime factors. For example, 12 = 2 * 2 * 3 has prime score 2, while 1 has prime score 0.
You may perform at most k operations. Return the maximum achievable score modulo 1000000007. Maximize the product before taking the modulo. Different subarrays may select the same element; only the subarray boundaries must be different.
Example 1:
Input: nums = [3,8]
k = 2
Output: 24Explanation: Both values have prime score 1. The subarrays [3], [8], and [3,8] select values 3, 8, and 3 respectively; the tie in [3,8] goes to the earlier index. The two best choices multiply to 8 * 3 = 24.
Example 2:
Input: nums = [6,5]
k = 2
Output: 36Explanation: The prime score of 6 is 2, while that of 5 is 1. Both [6] and [6,5] select 6, so choosing those two distinct subarrays gives 6 * 6 = 36.
Example 3:
Input: nums = [1,1,1]
k = 6
Output: 1Explanation: Every value is 1 with prime score 0. Each of the six nonempty subarrays contributes a factor of 1, so the score remains 1 even after all six operations.
Constraints:
1 <= nums.length <= 1000001 <= nums[i] <= 1000001 <= k <= min(nums.length * (nums.length + 1) / 2, 1000000000)