Câu lạc bộ Lập trình thi đấu của trường tổ chức ~n~ buổi thi thử hằng tuần, đánh số từ ~1~ đến ~n~ theo thứ tự thời gian. Điểm của bạn Lan ở buổi thi thứ ~i~ là ~a_i~.

Để viết bản tin cổ vũ phong trào, ban chủ nhiệm muốn chọn ra đúng ~k~ buổi thi sao cho, xét theo thứ tự thời gian, điểm của Lan ở buổi được chọn sau luôn cao hơn hẳn điểm ở buổi được chọn trước. Mỗi cách chọn như vậy được gọi là một chuỗi thăng tiến.

Nói chính xác, một chuỗi thăng tiến là một bộ ~k~ chỉ số ~1 \le i_1 < i_2 < \cdots < i_k \le n~ thoả mãn ~a_{i_1} < a_{i_2} < \cdots < a_{i_k}~. Hai chuỗi thăng tiến được coi là khác nhau nếu hai bộ chỉ số khác nhau, kể cả khi các điểm số tương ứng giống hệt nhau. Với ~k = 1~, mỗi buổi thi tự nó là một chuỗi thăng tiến.

Yêu cầu

Hãy đếm số chuỗi thăng tiến. Vì kết quả có thể rất lớn, chỉ cần đưa ra phần dư của nó khi chia cho ~10^9 + 7~.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~k~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~, các số cách nhau bởi dấu cách.

Kết quả ra

Ghi ra một số nguyên duy nhất là số chuỗi thăng tiến sau khi lấy phần dư cho ~10^9 + 7~.

Ràng buộc

~1 \le n \le 10^5~; ~1 \le k \le 10~; ~k \le n~; ~1 \le a_i \le 10^9~.

• Subtask 1 (10% số điểm – test 01–04): ~n \le 20~;
• Subtask 2 (20% số điểm – test 05–08): ~n \le 2000~;
• Subtask 3 (20% số điểm – test 09–12): ~k = 2~;
• Subtask 4 (20% số điểm – test 13–16): ~a_i \le 100~;
• Subtask 5 (30% số điểm – test 17–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

5 3
2 1 3 3 5

Kết quả ra mẫu 1

4

Giải thích

Có ~4~ chuỗi thăng tiến gồm ~3~ buổi thi, ứng với các bộ chỉ số ~(1, 3, 5)~, ~(1, 4, 5)~, ~(2, 3, 5)~ và ~(2, 4, 5)~; điểm số tương ứng là ~(2, 3, 5)~, ~(2, 3, 5)~, ~(1, 3, 5)~ và ~(1, 3, 5)~. Bộ chỉ số ~(3, 4, 5)~ không hợp lệ vì ~a_3 = a_4 = 3~, điểm không tăng; bộ ~(1, 2, 5)~ không hợp lệ vì ~a_1 > a_2~.