ami có một dãy số nguyên dương \(A\) gồm \(n\) phần tử và một số nguyên dương \(k\).

Các bạn có thể thực hiện thao tác sau không quá k lần, mỗi lần, các bạn có thể chọn một phần tử trong \(A\) và giảm giá trị của nó đi 1.

Hãy tìm cách thực hiện thao tác trên một cách tối ưu để trị tuyệt đối của tích \(A\) là nhỏ nhất. Nói cách khác, các bạn cần cực tiểu giá trị \(S\) sau:

\(S\) = |\(A_1 * A_2 * ... * A_n\)|

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) lần lượt là số phần tử của dãy \(A\) và số lần thực hiện thao tác tối đa.

• Dòng tiếp theo chứa \(n\) số nguyên dương \(A_i\) biểu thị một phần tử của dãy \(A\).

Output

• Hãy in ra giá trị \(S\) sau khi chia dư cho \(10^9+7\).

Scoring

• Trong toàn bộ dữ liệu có \(1 \leq a_i \leq 10^9\).

• \(50\)% điểm tương ứng với \(1 \leq n, m \leq 10\).

• \(50\)% điểm tương ứng với \(1 \leq n, m \leq 2*10^5\).

Example

3 3
1 2 3

0

2 1
2 2

2