Meet In The Middle

Nguồn: CSES

Cho tập ~S~ gồm ~n~ phần tử. Đếm xem có bao nhiêu cách chọn ra tập con có tổng bằng chính xác ~x~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~x~ ~(1 \le n \le 40,~ ~1 \le x \le 10^9)~.
• Dòng thứ hai chứa ~n~ phần tử nguyên dương của tập ~S~, có giá trị không vượt quá ~10^9~.

Output

• In ra số lượng tập con thỏa mãn.

Samples

4 5
1 2 3 2

3

Scoring

• Subtask ~1~ ~(40\%)~ số điểm: ~n \le 20~
• Subtask ~2~ ~(60\%)~ số điểm: Không còn ràng buộc gì thêm