Một dãy số gồm N phần tử, thực hiện các phép toán bằng cách chèn dấu cộng hoặc trừ vào giữa các phần tử ta được các giá trị khác nhau. Ví dụ dãy 4 phần tử: 1, 2, 3, 4 ta chèn các phép xen kẽ được phép tính 1 +2 -3 +4 = 4.

Cho dãy gồm N phần tử, hãy tính xem có bao nhiêu cách chèn các dấu để phép tính có giá trị bằng S.

Input: 

- Dòng dầu gồm số nguyên dương N (1≤N≤20) và giá trị S.

- Dòng tiếp theo chứa N phần tử a_i (0≤a_i≤10⁹).

Ouput: Số cách chèn thỏa mãn yêu cầu đề.

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

4 0
1 2 3 4

Output

1

Giải thích ví dụ

• Có 1 cách duy nhất là 1-2-3+4 = 0.