{"code":"21thtkvb2","name":"Tập số","description":"Alice và Bob đã tìm thấy kho báu, nhưng để mở được kho báu thì cả hai phải giải câu đố sau:\r\n\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 số $u,v$ ($u \\neq 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 số 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 mộ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 lấy dư.\r\n\r\n#### Input\r\n\r\n - 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 - 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    ???+ \"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        Có tất cả $2^4 = 16$ tập con của tập {$1,2,3,4$}. Tất cả các tập con đều thỏa mãn trừ các tập:\r\n        - {$1,4$}.\r\n        - {$1,2,4$}.\r\n        - {$1,3,4$}.\r\n        - {$1,2,3,4$}.","points":1900.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}}