<p>You are given an integer array <code>nums</code>, an integer <code>k</code>, and an integer <code>multiplier</code>.</p>

<p>You need to perform <code>k</code> operations on <code>nums</code>. In each operation:</p>

<ul>
	<li>Find the <strong>minimum</strong> value <code>x</code> in <code>nums</code>. If there are multiple occurrences of the minimum value, select the one that appears <strong>first</strong>.</li>
	<li>Replace the selected minimum value <code>x</code> with <code>x * multiplier</code>.</li>
</ul>

<p>After the <code>k</code> operations, apply <strong>modulo</strong> <code>10<sup>9</sup> + 7</code> to every value in <code>nums</code>.</p>

<p>Return an integer array denoting the <em>final state</em> of <code>nums</code> after performing all <code>k</code> operations and then applying the modulo.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [2,1,3,5,6], k = 5, multiplier = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">[8,4,6,5,6]</span></p>

<p><strong>Explanation:</strong></p>

<table>
	<tbody>
		<tr>
			<th>Operation</th>
			<th>Result</th>
		</tr>
		<tr>
			<td>After operation 1</td>
			<td>[2, 2, 3, 5, 6]</td>
		</tr>
		<tr>
			<td>After operation 2</td>
			<td>[4, 2, 3, 5, 6]</td>
		</tr>
		<tr>
			<td>After operation 3</td>
			<td>[4, 4, 3, 5, 6]</td>
		</tr>
		<tr>
			<td>After operation 4</td>
			<td>[4, 4, 6, 5, 6]</td>
		</tr>
		<tr>
			<td>After operation 5</td>
			<td>[8, 4, 6, 5, 6]</td>
		</tr>
		<tr>
			<td>After applying modulo</td>
			<td>[8, 4, 6, 5, 6]</td>
		</tr>
	</tbody>
</table>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [100000,2000], k = 2, multiplier = 1000000</span></p>

<p><strong>Output:</strong> <span class="example-io">[999999307,999999993]</span></p>

<p><strong>Explanation:</strong></p>

<table>
	<tbody>
		<tr>
			<th>Operation</th>
			<th>Result</th>
		</tr>
		<tr>
			<td>After operation 1</td>
			<td>[100000, 2000000000]</td>
		</tr>
		<tr>
			<td>After operation 2</td>
			<td>[100000000000, 2000000000]</td>
		</tr>
		<tr>
			<td>After applying modulo</td>
			<td>[999999307, 999999993]</td>
		</tr>
	</tbody>
</table>
</div>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= multiplier &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    # Imagine this: [2,1,3,5], k=50 m=7
    # k=1,we get [2,7,3,5]
    # k=2,we get [14,7,3,5]
    # k=3,we get [14,7,21,5]
    # k=4,we get [14,7,21,35]
    # wait a minute, [2,1,3,5] and [14,7,21,35] have the same order. i,e
    # smallest element is at index 1. Second smallest is at index 0, Third smallest is at index 2. Fourth smallest is at index 3.

    # Keep going.

    # k=5,we get [14,49,21,35]
    # k=6,we get [98,49,21,35]
    # k=7,we get [98,49,147,35]
    # k=8,we get [98,49,147,245]
    # .
    # wait a minute, [2,1,3,5] and [98,49,147,245] have the same order. i,e
    # smallest element is at index 1. Second smallest is at index 0, Third smallest is at index 2. Fourth smallest is at index 3.

    # k=9,we get [98,343,147,245]
    # k=10,we get [686,343,147,245]
    # .
    # .
    # .
    # The idea is that k=1 to k=4 is a cycle. k=5 to k=8 is a cycle.
    # We dont need to iterate these iterations in a while loop. We can find the number of cycles and immediately arrive at the end of these cycles.

    # So, we can go from k=1 to k=8, if we just multiply every number by multiplier**(2) = 7**2=49. 2 because there are 2 cycles from k=1 to k=8.

    # full_cycles can be found by full_cycles = k // n
    # left_over can be found by = k % n

    # How do we know if there is a cycles?
    # Well, if the smallest element (1 in [2,1,3,5]) in your original array suddenly becomes the largest element in the original array after you multiplied it with multiplier (i.e [2,7,3,5]), then there is a cycle. This is because, that means the second smallest element (2) will be multiplied with the multiplier (2*7=14) and larger than this (7), it will keep being always greater than the smallest element after the multiplication. Third smallest element will keep being greater than the second smallest element after the multiplication. Finally, fourth smallest element will keep being the fourth smallest element after the multiplication. The multiplication with 7 doesnt change the order of the array, hence we get cycle at every 4 iterations

    # So, in the brute force approach, if we see that there is a cycle (num*multiplier) > max of the array, lets just stop wasting time in the while loop and do the cycle count. We will count the full cycles and apply the left over iterations at the end. We can apply the left over iterations like we would in brute force.
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        if multiplier == 1:
            return nums
            
        mod = 10 ** 9 + 7
        max_num = max(nums)
        n = len(nums)

        min_heap = []

        for idx, num in enumerate(nums):
            heapq.heappush(min_heap, (num, idx))

        for _ in range(k):
            num, index = heapq.heappop(min_heap)
            nums[index] = num * multiplier
            heapq.heappush(min_heap, (nums[index], index))

            # deduct k when we start the first cycle
            k -= 1

            # break when we see a cycle
            if nums[index] > max_num:
                break
        
        num_of_cycle = k // n
        left_over = k % n

        y = pow(multiplier, num_of_cycle, mod)

        for _ in range(left_over):
            num, index = heapq.heappop(min_heap)
            nums[index] = (num * multiplier) % mod
        
        return [(num * y) % mod for num in nums]
19500