Bạn được cho một mảng gồm \(n\) số. Có bao nhiêu cách chọn tập hợp con các số có tổng \(x\)?

Input

Dòng đầu tiên là hai số \(n\) và \(x\) : kích thước mảng và tổng bắt buộc.

Dòng thứ hai chứa \(n\) số nguyên \(t_1,t_2,…, t_n\): các số trong mảng.

Output

In ra số cách bạn có thể tạo ra tổng \(x\).

Constraints

• \(1 \le n \le 40\)
• \(1 \le x \le 10^9\)
• \(1 \le t_i \le 10^9\)

Example

Input

4 5
1 2 3 2

Output

3