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

import heapq
from typing import List
class Solution:
  def __init__(self) -> None:
    self.heap = []
    self.answer = []
    self.touched = set()
    self.multiplier = None
    self.k = None
    self.moduler = 10 ** 9 + 7


  def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
    if multiplier == 1:
        return nums
    l = len(nums)
    self.touched = set()
    self.heap = []
    self.answer = [None] * l
    self.k = k
    self.multiplier = multiplier
    for i, num in enumerate(nums):
      self.heap.append((0, num, i))
    heapq.heapify(self.heap)
    self.operation()
    if not self.k:
      self.make_answer()
      return self.answer
    self.distribute()
    self.touched = set()
    self.operation()
    self.make_answer()
    return self.answer
  

  def operation(self):
    while self.k:
      self.k -= 1
      t, n, idx = heapq.heappop(self.heap)
      n *= self.multiplier
      if n > self.moduler:
        t += n // self.moduler
        n %= self.moduler
      self.touched.add(idx)
      heapq.heappush(self.heap, (t, n, idx))
      if len(self.touched) == len(self.heap):
        break
    return
  

  def distribute(self):
    l = len(self.heap)
    n = self.k // l
    self.k %= l
    M = self.mod_exp(self.multiplier, n, self.moduler)
    for i in range(l):
      t, num, idx = self.heap[i]
      self.heap[i] = (t, num * M, idx)
    return
  

  def make_answer(self):
    for t, num, i in self.heap:
      self.answer[i] = num % self.moduler
    return
  

  def mod_exp(self, a, b, n):
    if n == 1:
        return 0  # 모듈러가 1인 경우 결과는 항상 0

    # 페르마의 소정리 적용
    if b >= n:
        b = b % (n - 1)
    
    # 빠른 거듭제곱을 사용한 모듈러 계산
    result = 1
    a = a % n  # a를 n으로 미리 나눔
    while b > 0:
        # 만약 b가 홀수라면 result에 현재의 a를 곱해줌
        if (b % 2) == 1:
            result = (result * a) % n
        # b를 2로 나누고, a는 제곱
        b = b >> 1
        a = (a * a) % n
    return result
20800