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 \leq 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}\) \(\left( \left| a_{i} \right| \leq 10^{9} \right)\). Đếm số cách chia dãy \(a\) thành các dãy đẹp liên tiếp, chia dư cho \(\left( 10^{9} + 7 \right)\).

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\) \(\left( k \leq n^{3} \right)\) 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\) \(\left( n \leq 2 \times 10^{5},k \leq n^{3} \right)\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\) \(\left( \left| a_{i} \right| \leq 10^{9} \right)\), 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ụ:

Ràng buộc:

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 15\).

• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 100\).

• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 3000\).

• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.