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₁, d₂, … , 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₁, d₂, … , 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⁹ + 7.