Cho mảng A gồm N số nguyên dương. Hãy đếm số lượng tập con có tổng đúng bằng X. (\(Tập rỗng có tổng bằng 0 — tính nếu X = 0.\))

Với \(N \le 40\), duyệt toàn bộ \(2^N\) tập con là quá chậm. Sử dụng Meet in the Middle:

1. Chia mảng làm 2 nửa, sinh tất cả tổng tập con của mỗi nửa và đếm tần số bằng hash map.
2. Với mỗi tổng s ở nửa thứ nhất, tra hash map ở nửa thứ hai với key X - s.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên N (\(1 \le N \le 40\)) và X (\(1 \le X \le 10^18\)).
• Dòng thứ hai chứa N số nguyên dương \(A_i\) (\(1 \le A_i \le 10^15\)).

Đầu ra

Số lượng tập con có tổng đúng bằng X.

Ví dụ

Input:
6 26
2 3 5 8 13 21

Output:
4

Giải thích

4 tập con: {2,3,21}, {5,21}, {5,8,13}, {2,3,8,13}.

Ràng buộc & Subtasks