3556. Final Array State After K Multiplication Operations II

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        MOD = 10**9 + 7
        n = len(nums)
        
        if multiplier == 1:
            return [x % MOD for x in nums]
        
        import heapq
        
        # Use a min-heap with (value, index)
        heap = [(nums[i], i) for i in range(n)]
        heapq.heapify(heap)
        
        max_val = max(nums)
        
        # Phase 1: Simulate until all elements are >= max_val
        # This ensures we can predict the cycle
        ops_done = 0
        while ops_done < k:
            val, idx = heap[0]
            if val >= max_val:
                break
            heapq.heapreplace(heap, (val * multiplier, idx))
            nums[idx] = val * multiplier
            ops_done += 1
        
        remaining = k - ops_done
        
        if remaining == 0:
            return [x % MOD for x in nums]
        
        # Phase 2: Now all elements are >= max_val
        # Sort by value, then by index to determine order
        heap.sort(key=lambda x: (x[0], x[1]))
        
        # Each element will get remaining // n full cycles
        full_cycles = remaining // n
        extra_ops = remaining % n
        
        # Apply full cycles using modular exponentiation
        result = [0] * n
        
        for i, (val, idx) in enumerate(heap):
            # This element gets full_cycles + (1 if i < extra_ops else 0) more operations
            extra = 1 if i < extra_ops else 0
            total_mult = full_cycles + extra
            
            # val * multiplier^total_mult mod MOD
            result[idx] = (val % MOD) * pow(multiplier, total_mult, MOD) % MOD
        
        return result