分数: 366 分
问题陈述
高桥正在投资 N 股票问题。目前的估值 i- 第股票是 L_i 日元。
高桥将使用 K 投资机会一一按顺序排列。每次有机会,他都会选择其中之一 N 股票并将其当前估值翻倍。他可能会多次选择同一只股票。
确定所有的最大可能总估值 N 股票毕竟 K 投资机会已被使用,当他在每个机会中选择股票以最大化该总数时。
由于答案可能非常大,因此输出最大值模 10^9 + 7。请注意,仅在确定真正的最大值后才应用模运算。也就是说,您不应根据取模的中间结果来比较值 10^9 + 7;相反,找到作为真实(未模数)数字的最大值,然后输出该值模 10^9 + 7.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{18}
- 1 \leq L_i \leq 10^9
- 所有输入值均为整数。
输入
N K L_1 L_2 \ldots L_N
- 第一行包含一个整数 N 代表股票数量和一个整数 K 代表投资机会的数量,以空格分隔。
- 第二行包含整数 L_1, L_2, \ldots, L_N 代表每只股票的当前估值,以空格分隔。
输出
一行输出毕竟最大总估值 K 投资机会已被使用,取模 10^9 + 7.
示例输入 1
3 2 3 1 2
示例输出 1
15
示例输入 2
5 10 4 8 2 5 1
示例输出 2
8204
示例输入 3
4 1000000000000000000 1000000000 999999999 999999998 999999997
示例输出 3
963666195