Cho mảng \(a_1, a_2, \dots, a_n\) và số nguyên \(S\). Đếm số tập con có tổng \(\le S\).

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

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

Định dạng đầu ra

• Một số nguyên là số lượng tập con thỏa mãn.

Ví dụ

Input:

3 5
1 2 3

Output:

5

Ràng buộc

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