分数: 400 分
问题陈述
高桥正在成长 N 他农场里的果树。的初始增长水平 i第棵树 (1 \leq i \leq N) is A_i.
为准备收获季节,高桥计划准确分配 K 这些果树总共有袋肥料。让 B_i 表示给予的肥料袋数 i第棵树。分配必须满足以下条件:
- 每个 B_i 是一个非负整数。 (给一棵树的袋子数量没有上限。有些树根本不收到袋子也是可以接受的。)
- B_1 + B_2 + \cdots + B_N = K
施肥后,植物的生长水平 i第棵树变成 A_i + B_i。在这个农场中,已知收获产量是由所有果树的生长水平的乘积决定的,因此收获产量为
(A_1 + B_1) \times (A_2 + B_2) \times \cdots \times (A_N + B_N)
当高桥优化分配肥料以最大化收获产量时,找到最大收获产量模 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 A_i \leq 10^9
- 所有输入均为整数
输入
N K A_1 A_2 \cdots A_N
- 第一行包含一个整数 N 代表果树的数量和一个整数 K 代表肥料袋总数,以空格分隔。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 代表每棵果树的初始生长水平,以空格分隔。
输出
在一行中输出收获产量模数 10^9 + 7 高桥优化分配肥料以最大化收获产量后。
样本输入 1
3 5 1 2 3
示例输出 1
48
示例输入 2
4 3 2 2 5 8
示例输出 2
480
示例输入 3
8 100 1 7 3 20 15 2 9 30
示例输出 3
505781965
示例输入 4
20 1000000000000 1000000000 1 500000000 123456789 987654321 42 314159265 271828182 999999937 100 200 300 400 500 600 700 800 900 1000 12345
示例输出 4
134759236
示例输入 5
1 1000000000000000000 1000000000
示例输出 5
42