Cho 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\).

Hãy thực hiện thao tác sao cho không quá k lần, mỗi lầ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ầ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\).

Ví dụ 1:

Input

3 3
1 2 3

Output

0

Giải thích:

• Ở ví dụ 1, ta có thể áp dụng cả 3 thao tác lên số 3 để nhận được dãy [1 2 0]. Tích \(1 * 2 * 0 = 0.\)

Ví dụ 2:

Input

2 1
2 2

Output

2

Giải thích:

• Ở ví dụ 2, ta có thể áp dụng thao tác lên một trong 2 số. Đáp án sẽ luôn là 2.

Ràng buộc

• 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\).