Home Improvement

Mọi chuyện bắt đầu khi Chú Gấu nhận được bức ảnh kỷ niệm từ người bạn Hổ. Trong lúc Chú Gấu loay hoay treo ảnh, cô bé Masha tinh nghịch nhảy vào "giúp đỡ" khiến chiếc đinh bị cong. Chú Gấu dùng kìm kéo đinh ra nhưng lực kéo quá mạnh làm vỡ đường ống, gây ra một vụ nổ lớn làm phòng khách cháy đen thui.

Để sửa lại nhà, Chú Gấu cùng Masha trải qua chuỗi công việc đầy gian nan: từ sơn tường văng tung tóe, cho đến lúc Masha nhảy lên máy chà sàn rượt đuổi náo loạn cả khu rừng. Thấy vậy, các bạn Thỏ, Sóc, Nhím đã cùng nhau kéo đến trợ giúp dán giấy tường, giúp căn nhà trở nên đẹp đẽ rực rỡ. Tuy nhiên, ở đoạn kết, vừa khi Chú Gấu hân hoan cắm phích tivi để mời cả hội xem phim thì bình điện lại nổ tung, đưa căn nhà trở về trạng thái đen thui ban đầu!

Rút kinh nghiệm từ \(2\) vụ nổ liên tiếp, Chú Gấu quyết định kiểm tra lại hệ thống \(N\) thiết bị điện trong nhà. Thiết bị thứ \(i\) tiêu thụ công suất \(A_i\). Chú Gấu muốn chọn ra một nhóm thiết bị để bật sao cho tổng công suất tiêu thụ đúng bằng \(K\) để tránh quá tải.

Yêu cầu: Hãy tính số cách chọn nhóm thiết bị điện có tổng công suất bằng \(K\).

Input

• Dòng thứ nhất chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 100\), \(1 \le K \le 10^5\)) — số lượng thiết bị điện và công suất mục tiêu.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 1000\)) — công suất của từng thiết bị.

Output

• In ra một số nguyên duy nhất là số cách chọn nhóm thiết bị chia dư cho \(10^9 + 7\).

Example

4 5
2 3 5 1

2