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à một 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 \le 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| \le 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 qua ~k~ (~k \le n^3~) lần tráo đổi giá trị ở Bước 2.

Input

Vào từ tệp văn bản ~\texttt{NARR.INP}~ gồm:

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

Output

Ghi kết quả lên tệp văn bản ~\texttt{NARR.OUT}~

• 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

Scoring

• Subtask ~1\ (3\%):~ ~n \le 15~
• Subtask ~2\ (6\%):~ ~n \le 100~
• Subtask ~3\ (15\%):~ ~n \le 3000~
• Subtask ~4\ (20\%):~ Không có ràng buộc gì thêm

Sample Input 1

5 10
1 2 3 4 5

Sample Output 1

16

Sample Input 2

3 1
3 2 1

Sample Output 2

3