<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>

"""
Greedy.
Binary search.

大int*大int, 要注意long.

元素个数一定, 元素总和一定, 济贫最优 => 拉平尽量多的矮的.
(prefixSum[p] + k) / (p + 1) <= nums[p + 1]
=>
(p + 1) * nums[p + 1] - prefixSum[p] >= k
=>
diff[i] = i * nums[i] - prefixSum[i - 1], diff[i]表示拉平前i个元素到nums[i]需要的投资, 要求diff[i] <= k.
*/

/*
n = nums.length:
    TC = O(nlogn).
    AS = O(n):
        heap = O(n),
        stack = O(1).
"""


class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        MODULE = 10**9 + 7
        n = len(nums)
        nums.sort()
        prefixSum = [0] * n
        prefixSum[0] = nums[0]
        for i in range(1, n):
            prefixSum[i] = prefixSum[i - 1] + nums[i]
        diff = [0] * n
        for i in range(1, n):
            diff[i] = nums[i] * i - prefixSum[i - 1]
        i = self.binarySearch(diff, k, 0, n - 1)
        total = prefixSum[i] + k
        each = total // (i + 1)
        extra = total % (i + 1)
        res = 1
        for j in range(extra):
            res = (res * (each + 1)) % MODULE
        for j in range(extra, i + 1):
            res = (res * each) % MODULE
        for j in range(i + 1, n):
            res = (res * nums[j]) % MODULE
        return int(res)

    def binarySearch(self, diff, k, left, right):
        while left < right - 1:
            mid = left + (right - left) // 2
            if diff[mid] <= k:
                left = mid
            else:
                right = mid - 1
        if diff[right] <= k:
            return right
        else:
            return left

769