Cửa hàng có n món quà, món thứ i giá ai nghìn đồng. Bạn Minh có đúng S nghìn đồng và muốn chọn một số món (mỗi món tối đa một lần, chọn ít nhất một món) sao cho tổng giá đúng bằng S. Có bao nhiêu cách chọn?
Dữ liệu vào
Dòng đầu chứa n và S. Dòng thứ hai chứa n số nguyên dương a1…an.
Kết quả
Số cách chọn.
Giới hạn
1 ≤ n ≤ 18; 1 ≤ ai ≤ 10^6; 1 ≤ S ≤ 10^9.
Ví dụ 1 – vào
4 5 1 2 3 4
Ví dụ 1 – ra
2
Ví dụ 2 – vào
3 5 2 4 6
Ví dụ 2 – ra
0