D - 肥料の配分 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は農園で N 本の果樹を育てています。i 番目の果樹 (1 \leq i \leq N) の初期の成長度は A_i です。

高橋君は収穫シーズンに向けて、合計でちょうど K 袋の肥料をこれらの果樹に配分しようとしています。i 番目の果樹に与える肥料の袋数を B_i とするとき、以下の条件を満たすように配分しなければなりません。

  • 各 B_i は 0 以上の整数である。（1 本の果樹に与える肥料の袋数に上限はありません。また、1 袋も与えない果樹があっても構いません。）
  • 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
  • 1 行目には、果樹の本数を表す整数 N と、肥料の総袋数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各果樹の初期の成長度を表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

高橋君が収穫量を最大化するように最適に肥料を配分した後の収穫量を 10^9 + 7 で割った余りを、1行で出力せよ。

入力例 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

Score : 400 pts

Problem Statement

Takahashi is growing N fruit trees on his farm. The initial growth level of the i-th tree (1 \leq i \leq N) is A_i.

In preparation for the harvest season, Takahashi plans to distribute exactly K bags of fertilizer in total among these fruit trees. Let B_i denote the number of bags of fertilizer given to the i-th tree. The distribution must satisfy the following conditions:

  • Each B_i is a non-negative integer. (There is no upper limit on the number of bags given to a single tree. It is also acceptable for some trees to receive no bags at all.)
  • B_1 + B_2 + \cdots + B_N = K

After distributing the fertilizer, the growth level of the i-th tree becomes A_i + B_i. In this farm, it is known that the harvest yield is determined by the product of the growth levels of all fruit trees, so the harvest yield is

(A_1 + B_1) \times (A_2 + B_2) \times \cdots \times (A_N + B_N)

When Takahashi distributes the fertilizer optimally to maximize the harvest yield, find the maximum harvest yield modulo 10^9 + 7.

Note that the maximization is based on the true value before taking the modulo 10^9 + 7. That is, choose the distribution that maximizes the true harvest yield, and output that harvest yield modulo 10^9 + 7.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N K
A_1 A_2 \cdots A_N
  • The first line contains an integer N representing the number of fruit trees and an integer K representing the total number of bags of fertilizer, separated by a space.
  • The second line contains N integers A_1, A_2, \ldots, A_N representing the initial growth levels of each fruit tree, separated by spaces.

Output

Output in one line the harvest yield modulo 10^9 + 7 after Takahashi distributes the fertilizer optimally to maximize the harvest yield.

Sample Input 1

3 5
1 2 3

Sample Output 1

48

Sample Input 2

4 3
2 2 5 8

Sample Output 2

480

Sample Input 3

8 100
1 7 3 20 15 2 9 30

Sample Output 3

505781965

Sample Input 4

20 1000000000000
1000000000 1 500000000 123456789 987654321 42 314159265 271828182 999999937 100 200 300 400 500 600 700 800 900 1000 12345

Sample Output 4

134759236

Sample Input 5

1 1000000000000000000
1000000000

Sample Output 5

42