Sau một ngày mệt nhọc đón các đoàn về tham dự Trại hè tin học 2017, thầy Minh vô cùng mệt mỏi ngủ ngay khi học sinh về hết phòng. Trong giấc mơ, thầy Minh mơ đang vẽ một cây vô hạn, mỗi nút có đúng \(n\) nút con, khoảng cách từ nút cha tới các nút con của nó theo thứ tự từ trái sang phải là \(d_1, d_2, … , d_n\). Thầy Minh đang có một số \(k\) và rất muốn biết có bao nhiêu đỉnh trên cây mà khoảng cách từ đỉnh đó tới gốc không vượt quá \(k\).

Dữ liệu

• Dòng đầu chứa hai số nguyên dương \(n\) và \(k\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(d_1, d_2, … , d_n (d_i ≤ 100)\)

Kết quả

• Số lượng đỉnh mà khoảng cách từ đỉnh đó tới gốc không vượt quá \(k\). Đưa ra theo số dư cho \(10^9 + 7\).

Input

3 3 
1 2 3

Output

8

Giới hạn

• 50% test có \(k ≤ 10000, n ≤ 100\)
• 50% test có \(1000 < k ≤ 10^{18}, n≤ 100000\)

Nguồn: CĐ DHBB