{"code":"pvhoi4ii","name":"PVHOI 4 - II - THỨ TỰ TỪ ĐIỂN","description":"Cho dãy số $a_{1}, a_{2}, \\ldots, a_{n}$ và hai số $k$ và $s$. Bạn cần đếm số dãy số $b_{1}, b_{2}, \\ldots, b_{n}$ thoả mãn các điều kiện sau:\r\n- $b_{i} \\in \\{1, 2, \\ldots, s\\} \\ \\forall\\ 1 \\leq i \\leq n$.\r\n- Có chính xác $k$ cặp chỉ số $(l, r)$ sao cho $1 \\leq l \\leq r \\leq n$ và dãy số $a_{l}, a_{l + 1}, \\ldots, a_{r − 1}, a_{r}$ có thứ tự từ điển nhỏ hơn dãy số $b_{l}, b_{l + 1}, \\ldots, b_{r − 1}, b_{r}$.\r\n\r\nDo kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số dãy số thoả mãn khi chia cho $20215201314$.\r\n\r\nNhắc lại, dãy số $x_{1}, x_{2}, \\ldots, x_{m}$ có thứ tự từ điển nhỏ hơn dãy số $y_{1}, y_{2}, \\ldots, y_{m}$ khi và chỉ khi tồn tại chỉ số $\\alpha$ sao cho:\r\n- $1 \\leq \\alpha \\leq m, x_{\\alpha} < y_{\\alpha}$, và\r\n- $x_{\\beta} = y_{\\beta} \\ \\forall \\ 1 \\leq \\beta \\leq \\alpha − 1$.\r\n\r\n#### Input\r\n- Dòng đầu tiên chứa ba số nguyên $n, k$ và $s$ $(1 \\leq n \\leq 2014, 0 \\leq k \\leq 9213, 1 \\leq s \\leq 902535)$.\r\n- Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \\ldots, a_{n}$ $(1 \\leq a_{i} \\leq s)$.\r\n\r\n#### Output\r\n- Gồm một số nguyên duy nhất là phần dư của số dãy số tìm được khi chia cho $20215201314$.\r\n\r\n#### Scoring\r\n- Subtask $1$ ($10$ điểm): $n \\leq 8$ và $s \\leq 4$.\r\n- Subtask $2$ ($10$ điểm): $n \\leq 12$.\r\n- Subtask $3$ ($14$ điểm): $n \\leq 97$.\r\n- Subtask $4$ ($12$ điểm): $k = 0$.\r\n- Subtask $5$ ($12$ điểm): $k \\leq 5 \\times n$ và $a_{1} = a_{2} = \\ldots = a_{n} = 1$.\r\n- Subtask $6$ ($12$ đ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    ???+ \"Input\"\r\n        ```sample\r\n        4 6 3\r\n        2 3 2 1\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        7\r\n        ```\r\n    ??? warning \"Note\"\r\n        Trong ví dụ trên, có tất cả $7$ dãy số thoả mãn là $(2, 3, 3, 1), (3, 1, 2, 2), (3, 1, 2, 3), (3, 1, 3, 1), (3, 2, 2, 2), (3, 2, 2, 3)$ và $(3, 2, 3, 1)$.\r\n        Dãy số $(2, 3, 3, 1)$ thoả mãn vì ở đó có chính xác $6$ cặp chỉ số $(l, r)$ thoả mãn dãy số $a_{l}, a_{l + 1}, \\ldots, a_{r − 1}, a_{r}$ có thứ tự từ điển nhỏ hơn dãy số $b_{l}, b_{l + 1}, \\ldots, b_{r − 1}, b_{r}$. Đó là các cặp:\r\n        - $l = 1, r = 3$: $(2, 3, 2) < (2, 3, 3)$.\r\n        - $l = 1, r = 4$: $(2, 3, 2, 1) < (2, 3, 3, 1)$.\r\n        - $l = 2, r = 3$: $(3, 2) < (3, 3)$.\r\n        - $l = 2, r = 4$: $(3, 2, 1) < (3, 3, 1)$.\r\n        - $l = 3, r = 3$: $(2) < (3)$.\r\n        - $l = 3, r = 4$: $(2, 1) < (3, 1)$.\r\n\r\n        Dãy số $(3, 1, 3, 1)$ thoả mãn vì ở đó có chính xác $6$ cặp chỉ số $(l, r)$ thoả mãn các điều kiện ở trên:\r\n        - $l = 1, r = 1$: $(2) < (3)$.\r\n        - $l = 1, r = 2$: $(2, 3) < (3, 1)$.\r\n        - $l = 1, r = 3$: $(2, 3, 2) < (3, 1, 3)$.\r\n        - $l = 1, r = 4$: $(2, 3, 2, 1) < (3, 1, 3, 1)$.\r\n        - $l = 3, r = 3$: $(2) < (3)$.\r\n        - $l = 3, r = 4$: $(2, 1) < (3, 1)$.","points":2200.0,"partial":false,"time_limit":3.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}}