Anh Khoai được ông phú hộ hứa gả con giá với điều kiện làm việc không công cho ông ta mười năm và phải hoàn thành một nhiệm vụ ông ta giao cho. Sau mười năm làm việc anh Khoai tìm ông phú hộ để nhận nhiệm vụ cuối cùng. Vì không muốn gả con gái cho ông Khoai nên phú hộ yêu cầu anh mang về cho ông cây tre trăm đốt. Với sự giúp đỡ của ông bụt, anh Khoai đã mang về một trăm đốt tre cùng hai cầu thần chú "khắc nhập" và "khắc xuất" để hoàn thành nhiệm vụ. Tuy nhiên, bằng cách nào đó ông phú hộ đã biết được sự việc và chuẩn bị sẵn rất nhiều đốt tre dài ngắn khác nhau và yêu cầu anh tạo thành cây tre có độ dài ~K~ từ những đốt tre đã có sẵn thì ông ta mới gả con gái cho.

Yêu cầu

Hãy giúp anh Khoai kiểm tra xem có bao nhiêu cách tạo ra cây tre có độ dài ~K~ từ những đốt tre đã có sẵn.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa hai số nguyên là ~N~ và ~K~ ~(1 \le N, K \le 10^5)~ trong đó ~N~ là số đốt tre, ~K~ là chiều dài cây tre cần tạo thành.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ cách nhau một dấu cách lần lượt là chiều dài của ~N~ đốt tre ~(A_i \le 10^5)~.

Dữ liệu đầu ra

Gồm một số nguyên là số cách tạo thành cây tre có độ dài ~K~, chỉ cần in ra kết quả sau khi chia lấy dư cho ~10^9 + 7~.

Ràng buộc dữ liệu

• Subtask 1: 20% test có ~N \le 10^2~;
• Subtask 2: 40% test có ~N \le 10^3~;
• Subtask 3: 40% test không có ràng buộc gì thêm.

BỘ TEST KHÔNG KIỂM TRA CHO SUBTASK CUỐI CÙNG

Ví dụ

Ví dụ 1

INPUT

6 90
70 50 60 20 30 40

OUTPUT

4