Anh Khoai được ông phú hộ hứa gả con gái 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 anh 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.

Input

Đọc từ file văn bản TRE.INP có cấu trúc như sau:

• Dòng đầu tiên chứa 2 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 2 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)\).

Output

Ghi ra file văn bản TRE.OUT một số duy nhất 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\).

Scoring

• Subtask \(1: 20\%\) test có \(N \le 10^2\).
• Subtask \(2: 40\%\) test có \(N \le 10^3\).
• Subtask \(3: 40\%\) giới hạn gốc.

Example

6 90
70 50 60 20 30 40

4