{"code":"equa","name":"Phương trình","description":"Xét phương trình $𝑥_1 + 𝑥_2 + ⋯ + 𝑥_𝑘 = 𝑛$, trong đó $𝑥_1, 𝑥_2, … , 𝑥_𝑘$ là các biến nguyên dương thỏa\r\nmãn ràng buộc: $𝑥_𝑖 ≥ 𝑐_𝑖 > 0$.\r\n\r\n*Ví dụ:*\r\n\r\n$\\left\\{\\begin{matrix}\r\nx_1+x_2+x_3=7\\\\ \r\nx_1\\geq 1\\\\ \r\nx_2\\geq 2\\\\ \r\nx_3\\geq 3\r\n\\end{matrix}\\right.$\r\n\r\nPhương trình có ba nghiệm sau: $(1;2;4); (1;3;3); (2;2;3)$.\r\n\r\n**Yêu cầu**: Cho $𝑛, 𝑘, 𝑐_1, 𝑐_2, … , 𝑐_𝑘$, hãy đếm số nghiệm của phương trình.\r\n\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa 3 số nguyên dương $𝑛, 𝑘, 𝑀\\ (𝑀 \\le 10^9)$;\r\n- Dòng thứ hai gồm $𝑘$ số nguyên dương $𝑐_1, 𝑐_2, … , 𝑐_𝑘 (𝑐_𝑖 \\le 𝑛)$.\r\n\r\n

Output

\r\n\r\n- Gồm một dòng là số nghiệm của phương trình chia dư cho $𝑀$.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$: $𝑘 \\le 𝑛 \\le 20$;\r\n- Subtask $2$: $𝑘 \\le 𝑛 \\le 2000$;\r\n- Subtask $3$: $𝑘 \\le 𝑛 \\le 2000000$;\r\n\r\n

Example

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