{"code":"d13fset","name":"Tập số (THTB Vòng Khu vực 2021)","description":"Alice và Bob đã tìm thấy kho báu, nhưng để mở được kho báu cả hai phải giải câu đố sau:\r\nCho một số nguyên dương $n$, một tập con của tập {$1, 2, ... n$} gọi là tập $fset$ nếu không tồn tại hai\r\nsố $u, v (u \\ne v)$ thuộc tập mà $u \\times v$ là số chính phương. Số chính phương là bình phương của một\r\nsố nguyên. Hãy đếm số cách chọn tập $fset$ ? Hai cách chọn tập được gọi là khác nhau nếu tồn tại\r\nmột số xuất hiện trong cách chọn tập này nhưng không xuất hiện trong cách chọn tập kia.\r\n\r\n**Yêu cầu:** Cho $n, m$ gọi $s$ là số cách chọn tập $fset$, hãy tính $s$ % $m$, trong đó là phép toán chia %\r\nlấy dư.\r\n\r\n

Input

\r\n\r\n- Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương $n, m (m \\le 10^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ố là giá trị $s$ % $m$.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($16\\%$ số điểm): $n \\le 10$\r\n- Subtask $2$ ($24\\%$ số điểm): $n \\le 50$\r\n- Subtask $3$ ($16\\%$ số điểm): $n \\le 1000$\r\n- Subtask $4$ ($20\\%$ số điểm): $n \\le 10^5$\r\n- Subtask $5$ ($24\\%$ số điểm): $n \\le 10^6$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4 100\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 12\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Có tất cả $2^4=16$\r\n tập con của\r\n tập {1, 2, 3, 4}. Tất cả các tập\r\n con đều thỏa mãn trừ các tập:\r\n {1, 4}, {1, 2, 4}, {1, 3, 4}, {1, 2, 3, 4}","points":200.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}}