Bình làm quản lý kho tại một xưởng đóng gói nông sản ở huyện miền núi. Kho có \(N\) thùng hàng với khối lượng lần lượt là \(a_1, a_2, \ldots, a_N\). Hôm nay khách hàng đặt một đơn hàng yêu cầu chính xác \(S\) gam. Bình cần đếm xem có bao nhiêu cách chọn một số thùng hàng (mỗi thùng chọn nhiều nhất một lần) để tổng khối lượng các thùng được chọn đúng bằng \(S\). Hai cách chọn khác nhau khi tập chỉ số các thùng được chọn khác nhau.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(S\) (\(1 \le N \le 20\), \(1 \le S \le 2000\)).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le 100\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là số cách chọn nhóm thùng hàng có tổng khối lượng đúng bằng \(S\).

Ví dụ

Input:

4 5
1 2 3 4

Output:

2

Giải thích: Hai cách chọn là \(\{2, 3\}\) và \(\{1, 4\}\), mỗi tập đều có tổng bằng \(5\).

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 10\).
• \(30\%\) số điểm ứng với \(N \le 15\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.