Cho mảng \(a_1,\dots,a_n\) (\(n \le 15\)). Đếm số tập con khác rỗng có tổng bằng đúng \(S\).

Định dạng đầu vào

• Dòng đầu: \(n, S\) (\(1 \le n \le 15\), \(|S| \le 10^9\)).
• Dòng hai: \(n\) số \(a_i\).

Định dạng đầu ra

• Một số nguyên là số lượng tập con.

Ví dụ

Input:

5 5
1 2 3 2 1

Output:

3

Ràng buộc

• 100% số điểm: \(n \le 15\).