← 返回题目列表

AtCoder · awc0107_d

D. 肥料分配

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

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