C - Maximizing Investment Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 個の株式銘柄に投資しています。銘柄 i（1 \leq i \leq N）の現在の資産価値は S_i です。

高橋君はこれから、以下の操作をちょうど K 回行います。

  • N 個の銘柄の中から 1 つを選び、その銘柄の現時点での資産価値を 2 倍にする。

各回の操作で選ぶ銘柄は自由であり、同じ銘柄を複数回選ぶこともできます。同じ銘柄を複数回選んだ場合、2 倍にする操作はそのたびに累積的に適用されます。例えば、資産価値が S の銘柄を 3 回選んだ場合、その銘柄の資産価値は 2^3 \times S = 8S になります。

高橋君は、K 回の操作をすべて行った後の N 個の銘柄の資産価値の合計をできるだけ大きくしたいと考えています。

操作の対象とする銘柄の選び方を最適にしたとき、K 回の操作後における N 個の銘柄の資産価値の合計の最大値を求めてください。ただし、答えが非常に大きくなることがあるため、合計の最大値を 10^9 + 7 で割った余りを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • 1 \leq S_i \leq 10^9（1 \leq i \leq N）
  • 入力はすべて整数である

入力

N K
S_1 S_2 \ldots S_N
  • 1 行目には、銘柄の個数を表す整数 N と、操作の回数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各銘柄の操作前の資産価値を表す整数 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。

出力

K 回の操作を最適に行ったときの、N 個の銘柄の資産価値の合計の最大値を 10^9 + 7 で割った余りを 1 行で出力せよ。

入力例 1

3 2
1 3 2

出力例 1

15

入力例 2

4 3
5 5 1 2

出力例 2

48

入力例 3

10 20
12 7 25 3 18 30 1 9 14 22

出力例 3

31457391

入力例 4

40 123456789012345678
100000000 250000000 333333333 123456789 987654321 456789123 789123456 111111111 222222222 444444444 555555555 666666666 777777777 888888888 999999937 314159265 271828182 161803398 141421356 173205080 999999999 1 2 3 999999998 500000000 600000000 700000000 800000000 900000000 135791357 246802468 102030405 908070605 112233445 556677889 424242424 123123123 321321321 999000999

出力例 4

448506850

入力例 5

1 1000000000000000000
1000000000

出力例 5

963666222

Score : 366 pts

Problem Statement

Takahashi is investing in N stocks. The current asset value of stock i (1 \leq i \leq N) is S_i.

Takahashi will now perform the following operation exactly K times.

  • Choose one of the N stocks and double its current asset value.

He may freely choose which stock to select for each operation, and the same stock may be chosen multiple times. If the same stock is chosen multiple times, the doubling operation is applied cumulatively each time. For example, if a stock with asset value S is chosen 3 times, its asset value becomes 2^3 \times S = 8S.

Takahashi wants to maximize the total asset value of all N stocks after performing all K operations.

When the choice of stocks for the operations is made optimally, find the maximum possible total asset value of the N stocks after K operations. Since the answer can be very large, output the maximum total modulo 10^9 + 7.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N K
S_1 S_2 \ldots S_N
  • The first line contains an integer N representing the number of stocks and an integer K representing the number of operations, separated by a space.
  • The second line contains integers S_1, S_2, \ldots, S_N representing the asset values of each stock before the operations, separated by spaces.

Output

Output in one line the maximum total asset value of the N stocks when the K operations are performed optimally, modulo 10^9 + 7.

Sample Input 1

3 2
1 3 2

Sample Output 1

15

Sample Input 2

4 3
5 5 1 2

Sample Output 2

48

Sample Input 3

10 20
12 7 25 3 18 30 1 9 14 22

Sample Output 3

31457391

Sample Input 4

40 123456789012345678
100000000 250000000 333333333 123456789 987654321 456789123 789123456 111111111 222222222 444444444 555555555 666666666 777777777 888888888 999999937 314159265 271828182 161803398 141421356 173205080 999999999 1 2 3 999999998 500000000 600000000 700000000 800000000 900000000 135791357 246802468 102030405 908070605 112233445 556677889 424242424 123123123 321321321 999000999

Sample Output 4

448506850

Sample Input 5

1 1000000000000000000
1000000000

Sample Output 5

963666222