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 ≤ 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 ≤ N ≤ 40) và X (1 ≤ X ≤ 10^18).
• Dòng thứ hai chứa N số nguyên dương A_i (1 ≤ A_i ≤ 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}.