分数: 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