Overview

There are \(N\) stock issues, each with a given valuation. Using a total of \(K\) investment opportunities, you can double the valuation of any one stock issue each time. The problem asks for the maximum possible sum of final valuations.

Analysis

First, an investment opportunity is an operation that doubles a valuation, which causes exponential growth. Therefore, it is most effective to apply operations to the stock with the highest valuation.

For example, if stock A (valuation 100) and stock B (valuation 50) exist, and there are 2 investment opportunities: - Using both on A: 100 → 200 → 400, total is 400 + 50 = 450 - Using both on B: 50 → 100 → 200, total is 200 + 100 = 300

Thus, concentrating on the larger one is optimal.

In this way, it is optimal to use all operations on the stock with the highest valuation.

Therefore, we sort the given valuations in descending order, multiply the largest value by \(2^K\), and add the sum of all other stock valuations.

Also, since \(K\) can be very large (up to \(10^{18}\)), we cannot simply multiply by 2 a total of K times. Instead, we need to use exponentiation by squaring (\(2^K \bmod (10^9+7)\)).

Algorithm

1. Sort each stock’s valuation \(L_i\) in descending order.
2. For the largest valuation \(L_0\), compute \(2^K\) using exponentiation by squaring.
3. Compute the sum of valuations of all other stocks.
4. The final answer is: $\( (L_0 \times 2^K + \sum_{i=1}^{N-1} L_i) \bmod (10^9 + 7) \)$

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(1)\) (constant excluding input)

Implementation Notes

• In Python, using pow(base, exp, mod) enables fast modular exponentiation via exponentiation by squaring.
• Don’t forget to output the final result modulo \(10^9 + 7\).
• Be mindful of concentrating all operations on the largest element after sorting.

## Source Code

```python
MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    L = list(map(int, data[2:]))

    # Lを降順にソート
    L.sort(reverse=True)

    # 最大の要素に2^Kをかけるのが最適
    max_val = L[0]
    rest_sum = sum(L[1:]) % MOD if N > 1 else 0

    # powで2^K mod MODを高速計算
    power_of_2 = pow(2, K, MOD)
    
    # (max_val * 2^K) + sum of other elements
    max_contribution = (max_val % MOD) * power_of_2 % MOD
    result = (max_contribution + rest_sum) % MOD
    
    print(result)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.