← 返回题目列表

AtCoder · awc0063_c

C. 投资最大化

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥正在投资 N 股票。股票的当前资产价值 i (1 \leq i \leq N) 是 S_i.

Takahashi 现在将准确执行以下操作 K 次。

  • 选择其中一项 N 股票并使其当前资产价值翻倍。

他可以自由选择每次操作选择哪只股票,并且同一股票可以多次选择。如果多次选择同一股票,则每次都会累加加倍运算。例如,如果一只股票的资产价值 选择 S 被选中 3 倍,其资产价值变为 2^3 \times S = 8S.

高桥希望最大化所有资产的总价值 N 执行完所有操作后的股票 K 操作。

当操作的股票选择最优时,找到该股票的最大可能总资产价值 N 库存后 K 操作。由于答案可能非常大,因此输出最大总模数 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
  • 第一行包含一个整数 N 代表股票数量和一个整数 K 代表操作次数,以空格分隔。
  • 第二行包含整数 S_1, S_2, \ldots, S_N 代表每只股票操作前的资产价值,以空格分隔。

输出

一行输出该资产的最大总资产值 N 股票当 K 运算以最佳方式执行,模 10^9 + 7.


示例输入 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