Cho dãy số nguyên không âm gồm \(n\) phần tử: \(a_1,a_2,..., a_n\) và một số nguyên \(m\). Hãy thực hiện các thao tác thỏa mãn điều kiện sau:

• Không được thay đổi thứ tự các phần tử của danh sách này.
• Bạn phải chèn thêm một trong hai dấu \(\{+,-\}\) vào giữa các phần tử của tập hợp.
• Có \(n-1\) khoảng giữa các phần tử mà bạn có thể chèn dấu vào.

Ví dụ, với \(a=[3,4,5]\) bạn có thể thêm vào các dấu biến nó trở thành biểu thứ \(3+4-5\). Giá trị của biểu thức này là \(2\).

Hãy cho biết số lượng cách liệt kê cách chèn dấu mà giá trị của biểu thức được tạo ra là \(m\) .

Input

• Dòng thứ nhất chứa hai số nguyên \(n\), \(m\) \((1 \leq n \leq 20, |m| \leq 5*10^9)\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,..., a_n\) (\(|a_i| \leq 10^9\))

Output

• Gồm một dòng là số lượng cách liệt kê cách chèn dấu mà giá trị của biểu thức được tạo ra là \(m\) .

Ví dụ

Input

5 0
0 -4 -1 0 -3

Output

4

Giải thích

• \(0+4-1+0-3 = 0\)
• \(0+4-1-0-3 = 0\)
• \(0-4+1+0+3 = 0\)
• \(0-4+1-0+3 = 0\)