THỰC HÀNH

(Đề đề xuất DHBB 2017 của THPT CHUYÊN BIÊN HÒA – HÀ NAM)

Bờm rất muốn đi tham quan các danh lam thắng cảnh. Hè năm nay Bờm lựa chọn được n điểm tham quan đánh số từ 1 đến n, chi phí để tham quan điểm i là a_i. Bờm được mẹ cho số tiền là S. Hãy tính số cách chọn các điểm tham quan với tổng chi phí là S.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương n và S được ghi cách nhau một dấu cách.
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n, hai số liên tiếp được ghi cách nhau một dấu cách.

Dữ liệu ra:

            Một số nguyên duy nhất là số cách chọn các điểm tham quan của Bờm.

Ví dụ:

Dữ liệu vào:
4 4
1 2 3 4
Dữ liệu ra:
2

Giải thích: Có thể chọn tham quan điểm 1 và 3 hoặc tham quan điểm 4 (hai cách)

Giới hạn: 1 ≤ n ≤ 40; 1 ≤ S ≤ 2.10⁹; 1 ≤ a_i ≤ 10⁹.