{"code":"d13pnum","name":"Số hoàn hảo (THTC Vòng Khu vực 2021)","description":"Một bài toán trong đại hội Toán-Tin của Thiên hà như sau: Xét các số nguyên dương có dạng $a_1a_2...a_n$ , trong đó $a_i$ nhận giá trị $1$ từ đến $k$ . Một đoạn chữ số từ vị trí thứ $L$ đến vị trí thứ $L + 9$ được gọi là đoạn hoàn hảo nếu:\r\n\r\n1) $a_L + a_{L + 1} + ... + a_{L + 9} = 20$;\r\n2) Các chữ số $a_L, a_{L + 1}, ..., a_{L + 9}$ có thể chia làm $2$ nhóm có tổng bằng nhau.\r\n\r\n**Yêu cầu:** Cho $n, k$ và $m$ vị trí $p_1, p_2,..., p_m$, hãy đếm số lượng số nguyên dương có dạng $a_1a_2...a_n$ ($a_i$ nhận giá trị từ $1$ đến $k$) mà có $m$ đoạn hoàn hảo lần lượt bắt đầu từ $p_1, p_2,..., p_m$.\r\n\r\n

Input

\r\n\r\nVào từ thiết bị vào chuẩn:\r\n- Dòng đầu gồm bốn số nguyên dương $n, k, m, D$ $(9 < n \\le 50; k \\le 9; D \\le 10^9)$.\r\n- Dòng thứ hai gồm $m$ số nguyên $p_1, p_2,..., p_m$ $(1 \\le p_1 < p_2 < \\dots < p_m \\le n - 9)$.\r\n\r\n

Output

\r\n\r\n- Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên $r$, trong đó $r$ là phần dư của số lượng số thỏa mãn chia cho $D$.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($20\\%$ số điểm): $m = 1$;\r\n- Subtask $2$ ($20\\%$ số điểm): $m = 2$;\r\n- Subtask $3$ ($60\\%$ số điểm): $m \\le 5$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 15 2 2 123\r\n 1 3\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 8\r\n ```","points":2100.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"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}}