← 返回题目列表

AtCoder · awc0057_c

C. 投资加倍

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

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