Thuật toán sắp xếp nổi bọt để sắp xếp không giảm một dãy số nguyên \(b\) độ dài \(m\), có thể được mô tả như sau:

• Bước 1: nếu dãy \(b\) là dãy không giảm thì kết thúc thuật toán;
• Bước 2: Chọn một vị trí \(i (1≤i<m)\) nhỏ nhất mà \(b_i>b_{i+1}\), tráo đổi giá trị của hai phần tử \(b_i\) và \(b_{i+1}\). Tiếp tục quay lại Bước \(1\).

Cho một dãy số nguyên \(a\) độ dài \(n\), số thứ \(i\) là \(a_i (|a_i |≤10^9 )\). Đếm số cách chia dãy \(a\) thành các dãy đẹp liên tiếp, chia dư cho \((10^9+7)\).

Một dãy liên tiếp được gọi là dãy đẹp nếu số bước để sắp xếp không giảm dãy đó bằng thuật toán sắp xếp nổi bọt nêu trên, sử dụng không quá \(k (k≤n^3 )\) lần tráo đổi giá trị ở Bước \(2\).

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k (n≤2×10^5,k≤n^3 )\);
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (|a_i |≤10^9 )\), các số cách nhau bởi ít nhất một dấu cách.

Kết quả:

• Gồm một số nguyên duy nhất là số cách chia dãy \(a\) thành các dãy đẹp liên tiếp thỏa mãn yêu cầu đề bài.

Ví dụ:

Input 1

5 10
1 2 3 4 5

Output 1

16

Input 2

3 1
3 2 1

Output 2

3

Ràng buộc:

• Subtask 1 (10% số điểm): \(n≤15\);
• Subtask 2 (20% số điểm): \(n≤100\);
• Subtask 3 (30% số điểm): \(n≤3000\);
• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm.