Nhật là một đại gia với lượng tài sản khổng lồ. Nhật không thể mang theo toàn bộ số tiền của mình, nên hôm nay Nhật chỉ mang ~N~ mệnh giá khác nhau, bao gồm ~10^{100}~ tờ tiền có mệnh giá ~a_1~ đồng, ~10^{100}~ tờ tiền có mệnh giá ~a_2~ đồng, ..., ~10^{100}~ tờ tiền có mệnh giá ~a_N~ đồng.

Nhật muốn mua một mảnh đất có trị giá là ~K~. Với số tiền mà Nhật mang đi hôm nay, hãy tính số cách mà Nhật có thể mua mảnh đất.

Hai cách mua được coi là khác nhau nếu tồn tại một mệnh giá mà một cách mua sử dụng nhiều hoặc ít tờ tiền hơn cách mua còn lại.

Do số cách mua có thể rất lớn, hãy in ra phần dư của số cách mua sau khi chia lấy cho ~10^9 + 7~.

Yêu cầu: Tính số cách chọn số lượng tờ tiền cho mỗi mệnh giá sao cho tổng giá trị bằng ~K~, in kết quả theo modulo ~10^9 + 7~.

Input

• Dòng đầu tiên ghi 2 số nguyên ~N, K~ (~1 \le N \le 5000, 1 \le K \le 10^{18}~).
• Dòng tiếp theo gồm ~N~ số nguyên phân biệt ~a_1, a_2, \dots, a_N~ (~1 \le a_i \le K~).

Output

• In ra phần dư của đáp án của bài toán khi chia cho số ~(10^9 + 7)~.