Trong máy ATM còn ~n~ tờ tiền đánh số từ ~1~ tới ~n~, tờ tiền thứ ~i~ có mệnh giá là ~a_i~.

Hỏi nếu có lệnh rút số tiền là ~m~, máy có bao nhiêu cách trả bằng các tờ tiền đã cho?

Hai cách trả được gọi là khác nhau nếu có một tờ tiền được dùng để trả trong một cách nhưng không được dùng để trả trong cách còn lại.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, m~ ~(n \le 40; m \le 10^9)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(a_i \le 10^9)~.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

• In ra một số nguyên duy nhất là số cách trả tiền.

Sample Input

5 10
1 2 3 4 5

Sample Output

3

Notes

Có ~3~ cách trả:

• ~10 = 1 + 2 + 3 + 4~
• ~10 = 1 + 4 + 5~
• ~10 = 2 + 3 + 5~