Bờm đang háo hức được tham dự cuộc thi Olimpic năm nay được tổ chức tại thành phố Ninh Bình. Là một người đam mê khám phá các phong cảnh đẹp, Bờm đã tìm hiểu các khu du lịch ở thành phố này như khu du lịch Tràng An, chùa Bái Đính, đền thờ vua Đinh vua Lê, Rừng Cúc Phương … cũng như chi phí khi vào thăm. Giả sử có ~n~ điểm du lịch đánh số ~1 \dots n~, điểm du lịch ~i~ có chi phí vào thăm là ~a_i~. Hiện tại, Bờm được mẹ cho số tiền ~S~.

Yêu cầu: Hãy giúp Bờm tính số cách khác nhau có thể thăm quan sao cho tổng chi phí là ~S~. Các cách đi là hoán vị của nhau chỉ tính là một cách. Trong mỗi cách đi, mỗi điểm du lịch được thăm không quá 1 lần.

Input

• Dòng đầu chứa hai số nguyên dương ~n, S~ (~n \le 40, S \le 2 \cdot 10^9~).
• Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^9~).

Output

• Ghi một số nguyên duy nhất là số cách đi của Bờm. Trong trường hợp không có cách đi nào, dữ liệu in ra số -1.

Sample Input 1

4 4
1 2 3 4

Sample Output 1

2