Hôm nay bin9638, người mạnh nhất dòng họ Joseph, đang có trận chiến với boss cuối Dio để giải cứu crush của anh là Jisoo, để đánh bại Dio thì bin9638 phải giải bài toán sau.
Bài toán là cho \(1\) dãy số nguyên dương \(A_1, A_2,….,A_n (A_i≤10^6, n≤10^5)\). Bộ chỉ số “The world” của dãy A là bộ các chỉ số \(i_1<i_2<i_3…<i_k\) \((2 ≤ k ≤ 10,i_j ≤ n)\) sao cho \(A_{i1}<A_{i2}, A_{i2}>A_{i3}, A_{i3}<A_{i4}, A_{i4}>A_{i5},….\) Cụ thể là \(A_{ij} < A_{ij+1}\) với \(j\) lẻ và ngược lại với \(j\) chẵn. bin9638 cần bạn giúp đếm tất cả bộ chỉ số “The world” của dãy \(A\), hai bộ chỉ số sẽ khác nhau nếu có 1 vị trí trong hai bộ có chỉ số khác nhau. bin9638 tuy rằng có stand mạnh nhất thế giới nhưng cậu ấy lại khá ngu toán. Hãy giúp cậu ấy nhé !

Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho \(10^9+7\).

Yêu cầu: đếm số lượng bộ chỉ số “The world” của dãy \(A\).

Input

• Dòng đầu tiên lần lượt là \(n, k\).

• Dòng tiếp theo là dãy \(A\).

Output

• 1 số duy nhất là kết quả.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(k=2, n \le 1000\).

• Subtask \(2\) (\(60\%\) số điểm) không có ràng buộc gì thêm.

Example

4 3
1 2 1 5

1

Giới hạn:

• 40% test có \(k=2, n≤1000\).

• 60% test không có ràng buộc gì thêm.