Per có một bài toán như sau:

Cho trước một mảng ~a~ gồm ~n~ số nguyên và một số nguyên ~x~.

Hãy đếm số lượng tập con của mảng ~a~ có tổng bằng ~x~. Hai tập con được coi là khác nhau nếu tập chỉ số của chúng khác nhau, kể cả khi các giá trị được chọn là giống hệt nhau.

Đề bài ngắn gọn nhưng rất hay. Các bạn học viên hãy thử sức nhé!

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~x~ — số lượng phần tử của mảng ~a~ và tổng cho trước.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ — mô tả mảng ~a~.

Kết quả

In ra một số nguyên duy nhất — số tập con có tổng bằng ~x~.

Ví dụ

Đầu vào:

5 3
1 3 1 2 6

Đầu ra:

3

Giải thích: Có ~3~ tập con có tổng bằng ~x = 3~, đó là ~\{a_1, a_4\}~, ~\{a_3, a_4\}~ và ~\{a_2\}~.

Giới hạn

• ~1 \le n \le 40~
• ~1 \le x \le 10^9~
• ~1 \le a_i \le 10^9~

Vì ~a_i \ge 1~ nên tập rỗng không bao giờ được tính. Với ~n = 40~, hãy chia mảng làm hai nửa, liệt kê tổng của mọi tập con trong từng nửa rồi ghép chúng lại.