Cân thằng bằng đã từng rất phổ biến trong xã hội loài người, vì tính đơn giản của nó. Cấu tạo của cân gồm hai đĩa \(A, B\) được đặt ở hai đầu của một đòn bẩy.

Có \(n\) quả cân, quả thứ \(i\) có khối lượng \(m_i\). Để cân một vật, người ta đặt nó vào đĩa \(A\), sau đó thêm một vài quả cân vào các đĩa sao cho cân thăng bằng. Lúc này, cân nặng của vật là tổng khối lượng các quả cân trên đĩa \(B\) trừ đi tổng khối lượng các quả cân trên đĩa \(A\), vì cân chỉ thăng bằng khi tổng khối lượng trên đĩa \(A\) bằng tổng khối lượng trên đĩa \(B\).

Tuần trước, con chim vừa chở người em đi lấy vàng về, người em tiến hành cân lại số vàng mình nhận được. Để thuận tiện, anh ấy sẽ để nguyên túi vàng và cân một lần thay vì phải tách số vàng ra. Sau khi cân, anh ấy biết chính xác rằng túi vàng nặng \(M\).

Sau đó, vì tò mò và đam mê thuật toán, anh ấy thắc mắc là liệu có bao nhiêu cách cân khác nhau? Cụ thể hơn, bạn được cho một vật có khối lượng \(M\), bạn đặt nó vào đĩa \(A\) sau đó thêm một số quả cân vào các đĩa sao cho cân thăng bằng. Cần đếm số cách khác nhau để thêm các quả cân như trên. Hai cách được coi là khác nhau nếu tồn tại \(i\), \(1 ≤ i ≤ n\), sao cho hoặc là trong cách này thì sử dụng quả cân thứ \(i\) còn trong cách kia thì không, hoặc là cả hai cách đều sử dụng quả cân thứ \(i\) nhưng đặt vào hai đĩa khác nhau.

Input

• Dòng đầu chứa: \(n, M\)
• Dòng tiếp theo chứa dãy \(m\)

Output

• Một số nguyên duy nhất là kết quả bài toán

Constraints

• \(n ≤ 20\), \(1 ≤ m_i\) , \(M\) ≤ \(10^6\) ;

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10\)

Example

6 10
1 2 3 4 5 6 

17