Tý phụ mẹ bán hàng ở cửa hàng tạp hoá nhỏ gần nhà. Trong ngăn kéo của mẹ có rất nhiều đồng xu thuộc \(N\) loại mệnh giá khác nhau, gọi là \(c_1, c_2, \dots, c_N\), mỗi loại có số lượng không giới hạn vì khách hay đến đổi. Một hôm, có khách mua đồ hết đúng \(S\) đồng và đưa tờ tiền mệnh giá \(S\). Mẹ Tý muốn trả lại cho khách số tiền thừa bằng các đồng xu có sẵn, và hỏi có bao nhiêu cách kết hợp các đồng xu để gộp đúng thành \(S\) đồng.

Tý tò mò muốn giúp mẹ đếm nhưng thấy số cách quá nhiều nên hoa cả mắt. Hãy giúp Tý đếm và chỉ in ra phần dư khi chia cho \(10^9 + 7\).

Định dạng đầu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(S\) (\(1 \le N \le 500\), \(1 \le S \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(c_1, c_2, \dots, c_N\) (\(1 \le c_i \le 10^5\)).

Định dạng đầu ra

• In ra số cách tạo ra tổng \(S\), lấy phần dư khi chia cho \(10^9 + 7\).

Ví dụ

Input:

3 5
1 2 5

Output:

4

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 5\), \(S \le 100\).
• \(30\%\) số điểm ứng với \(N \le 100\), \(S \le 5000\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.