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$