Overview

When each operation allows you to “double the value of a chosen stock,” we consider which stock to choose to maximize the final total value, and compute the maximum modulo \(10^9+7\).

Analysis

How much a single operation increases the total

If you double a stock currently worth \(x\), it changes from \(x \to 2x\), so the total increases by exactly \(+x\) (the increase equals the original value \(x\)).

In other words, the profit (increase in total) gained from each operation is “the current value of the chosen stock.”

So which stock should we choose each time?

Since the increase each time equals the value of the chosen stock, choosing the stock with the largest value at that moment maximizes the increase for that operation.

Furthermore, what’s important is that doubling the largest stock makes it even larger for subsequent operations, allowing for greater increases in the future. Intuitively:

• The more you grow a large stock, the greater the increase you get from the next operation
• Even if you double a small stock, the increase for that round is small, and you lose the opportunity to grow the largest stock

For these reasons, it is optimal to concentrate all operations on the stock with the (initially) largest value.

Concrete Example

When \(S=[3,5,4],\ K=2\), the maximum is \(5\).

• Choose the maximum (5) both times: 1st increase \(+5\), 2nd increase \(+10\), total increase \(15\)
• Choose 5 once and 4 once: Increases of \(+5\) and \(+4\) for a total increase of \(9\) (smaller)

As shown, it is most profitable to keep growing the largest stock.

Why a naive approach doesn’t work

Since \(K\) can be up to \(10^{18}\): - “Simulating \(K\) operations” → \(O(K)\), which is far too slow. - Values grow exponentially, so they become extremely large with standard integers.

Therefore, we need to compute the result using a formula all at once, with modular arithmetic.

Algorithm

Let \(m=\max(S)\) be the initial value of the largest stock, and \(A=\sum S_i\) be the initial total.

If we double only the largest stock \(K\) times, its value becomes: - \(m \to 2^K m\)

The total becomes: - Final total \(= (A - m) + 2^K m = A + m(2^K - 1)\)

Therefore, the answer is: - \(\left(\sum S_i + \max(S)\cdot(2^K-1)\right) \bmod (10^9+7)\)

\(2^K \bmod MOD\) is computed using fast exponentiation (e.g., Python’s pow(2, K, MOD)).

Complexity

• Time complexity: \(O(N)\) (just finding the maximum and the sum)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• Since \(K\) can be very large, always use modular exponentiation like pow(2, K, MOD).

• To avoid \(2^K-1\) becoming negative, handle it as (p2 - 1) % MOD (which is what the code does).

• Take % MOD at each step to avoid overflow (even though Python can handle arbitrarily large numbers, this avoids heavy computation).

  Source Code

import sys

MOD = 10**9 + 7

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    S = data[2:2+N]

    mx = max(S)
    sm = sum(S) % MOD
    p2 = pow(2, K, MOD)

    ans = (sm + (mx % MOD) * ((p2 - 1) % MOD)) % MOD
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.