<p>You are given an array of non-negative integers <code>nums</code> and an integer <code>k</code>. In one operation, you may choose <strong>any</strong> element from <code>nums</code> and <strong>increment</strong> it by <code>1</code>.</p>

<p>Return<em> the <strong>maximum</strong> <strong>product</strong> of </em><code>nums</code><em> after <strong>at most</strong> </em><code>k</code><em> operations. </em>Since the answer may be very large, return it <b>modulo</b> <code>10<sup>9</sup> + 7</code>. Note that you should maximize the product before taking the modulo.&nbsp;</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,4], k = 5
<strong>Output:</strong> 20
<strong>Explanation:</strong> Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [6,3,3,2], k = 2
<strong>Output:</strong> 216
<strong>Explanation:</strong> Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length, k &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        # Given integers x1 <= x2 <= ... <= xn
        # Incrementing x1 will increment the total product by (x2 * ... * xn)
        # Obviously, we need to prioritize incrementation on the least number to maximize the increment on total product in one operation.
        # For k operations:
        # 1. The final result is irrelevant to the sequence of incrementing, so we can rearrange the increment.
        # 2. To compare two increment solutions, we can omit the increments on the same elements and then it leaves us to increments to different sets of numbers with the same operation numbers (<= k).
        # Based on the conclusion above, we should increment to the least numbers as possible to maximize the final product, hence the one with increments to greater numbers must NOT be optimal. Hence we need to greedily increment least numbers even for k-operations (k > 1).
        MOD = 10 ** 9 + 7
        nums.sort()
        # Append a dummy large number
        nums.append(10**10 + 1)
        ps = 0
        for i in range(len(nums) - 1):
            # How many elements are needed to fill nums[0:(i + 1)] with nums[i + 1]
            ps += nums[i]
            miss = nums[i + 1] * (i + 1) - ps
            if miss < k:
                continue
            else:
                total = k + ps
                base = total // (i + 1)
                rem = total % (i + 1)
                for j in range(i + 1):
                    nums[j] = base
                    if rem > 0:
                        nums[j] += 1
                        rem -= 1
                break
        ans = 1
        for i in range(len(nums) - 1):
            ans = (ans * nums[i]) % MOD
        return ans

740