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 ba 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 < 10, |m| \leq 10^{18})\)
• 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ụ

Ví dụ 1

Input

5 0
4 1 2 3 10

Output

3

Giải thích

• \(4*1+2*3-10 = 0\)
• \(4+1*2*3-10 = 0\)
• \(4+1+2+3-10 = 0\)

Ví dụ 2

Input

5 42
10 5 4 6 2

Output

3

Giải thích

• \(10*5+4-6*2 = 42\)
• \(10*5-4-6+2 = 42\)
• \(10+5*4+6*2 = 42\)