Cho mảng ~N~ số nguyên không âm và một số nguyên ~T~. Với mỗi phần tử ~a_i~, bạn gán cho nó dấu ~+~ hoặc ~-~. Hãy đếm số cách gán dấu sao cho tổng đại số bằng ~T~.

Ví dụ với mảng ~[1, 1, 1, 1, 1]~ và ~T = 3~:

• ~+1 +1 +1 +1 -1 = 3~
• ~+1 +1 +1 -1 +1 = 3~
• ... tổng cộng ~5~ cách.

Kết quả lấy modulo ~10^9 + 7~.

Input

• Dòng đầu gồm hai số nguyên ~N~ và ~T~ (~1 \le N \le 30~, ~|T| \le 30000~).
• Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ (~0 \le a_i \le 1000~).

Output

In ra số cách gán dấu modulo ~10^9 + 7~.

Ví dụ

Input 1

5 3
1 1 1 1 1

Output 1

5

Input 2

3 0
1 2 3

Output 2

2

Giải thích 2

Hai cách: ~+1-2+1 \cdot ... ~. Cụ thể: ~+1+2-3 = 0~ và ~-1-2+3 = 0~.

Giới hạn

Gợi ý

Gọi ~P~ là tập các phần tử được gán dấu ~+~, ~Q~ là tập phần tử được gán dấu ~-~. Ta có ~\text{sum}(P) - \text{sum}(Q) = T~ và ~\text{sum}(P) + \text{sum}(Q) = \text{total}~. Suy ra ~\text{sum}(P) = \frac{T + \text{total}}{2}~.