Bài 3 : Đào xuân (6.0 điểm)

Mùa xuân về trên rẻo cao, những gốc đào rừng bắt đầu trổ hoa rực rỡ. Trên một cành đào cổ thụ có \(n\) chùm hoa nằm dọc theo cành cây, các chùm hoa được đánh số thứ tự từ \(1\) đến \(n\). Chùm hoa thứ \(i\) có đúng \(a_i\) cánh hoa.

Lễ hội mùa xuân chỉ cho phép du khách chiêm ngưỡng những "đoạn hoa liên tiếp". Tuy nhiên, để bảo vệ vẻ đẹp tự nhiên, ban quản lý quy định: Một đoạn các chùm hoa liên tiếp từ vị trí \(i\) đến \(j\) \((1 \le i \le j \le n)\) chỉ được coi là "đoạn hoa hài hòa" nếu tổng số cánh hoa của tất cả các chùm trong đoạn đó không vượt quá số nguyên dương \(k\).

Yêu cầu: Em hãy giúp các bạn nhỏ vùng cao tính tổng số cánh hoa của tất cả các "đoạn hoa hài hòa" hiện có trên cành đào. Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo \(10^9 + 7\).

Input

Vào từ tệp văn bản SUMSUB.INP theo cấu trúc:

• Dòng đầu tiên ghi hai số nguyên dương \(n\) và \(k\) \((1 \le n \le 10^6; 1 \le k \le 10^9)\)
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) đại diện cho số cánh hoa của mỗi chùm hoa \((1 \le a_i \le 10^9)\)

Output

Ghi ra tệp văn bản SUMSUB.OUT một số nguyên duy nhất là tổng số cánh hoa tìm được theo modulo \(10^9 + 7\).

Example

3 5
2 3 4

14

Scoring

• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài với \(n \le 300\);
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài với \(n \le 2 \times 10^3\);
• Có \(15\%\) số test ứng với \(15\%\) số điểm của bài với tất cả các chùm hoa đều có đúng 1 cánh \((a_i = 1)\);
• Có \(15\%\) số test ứng với \(15\%\) số điểm của bài với tổng toàn bộ cánh hoa trên cành không vượt quá \(k\);
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.