Cho 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\). Cho một số \(k\).

Yêu cầu: Tính số lượng đỉnh trên cây mà khoảng cách từ đỉnh đó tới gốc không vượt quá \(k\).

Input

• 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)\).

Output

• Ghi 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\)

Ràng buộc

• Subtask 1: \(50%\) test có \(k ≤ 1000\)

• Subtask 2: \(50%\) test có \(1000<k≤10^{18}\)

Sample Input

3 3
1 2 3

Sample Output

8

Tag: NMT