{"code":"bossfight","name":"Đánh Boss","description":"Hôm nay [user: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ì [user:bin9638] phải giải bài toán sau.\r\nBà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. [user: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. [user: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é ! \r\n\r\n\r\nVì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho $10^9+7$.\r\n\r\n\r\n**Yêu cầu:** đếm số lượng bộ chỉ số “**The world**” của dãy $A$.\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên lần lượt là $n, k$.\r\n\r\n- Dòng tiếp theo là dãy $A$.\r\n\r\n#### Output \r\n- 1 số duy nhất là kết quả.\r\n\r\n#### Scoring\r\n\r\n- Subtask $1$ ($40\\%$ số điểm): $k=2, n \\le 1000$.\r\n\r\n- Subtask $2$ ($60\\%$ số điểm) không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 3\r\n        1 2 1 5\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        ```\r\n    \r\n    ??? warning \"Note\"\r\n\r\n        bộ chỉ số duy nhất là $[1,2,3]$\r\n\r\n\r\n**Giới hạn:**\r\n\r\n- 40% test có $k=2, n≤1000$.\r\n\r\n- 60% test không có ràng buộc gì thêm.","points":400.0,"partial":false,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}