{"problem":{"name":"[AHOI2022] 山河重整","description":{"content":"生活在 $998244353$ 号小宇宙的艾和兰收到了归零者的讯息，决定响应回归运动。他们需要把大部分的物质归还给大宇宙，只留下极少的物质用于在新宇宙重建自己的文明。 艾和兰的文明总共有 $n$ 个关键信息，编号为 $1, 2, \\ldots, n$。他们需要保留的信息是这些关键信息的一个子集 $S$。对于一个编号为 $x$ 的信息，只要 $S$ 中一个子集的编号和等于 $x$，那么他们设计的漂","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8340"},"statements":[{"statement_type":"Markdown","content":"生活在 $998244353$ 号小宇宙的艾和兰收到了归零者的讯息，决定响应回归运动。他们需要把大部分的物质归还给大宇宙，只留下极少的物质用于在新宇宙重建自己的文明。\n\n艾和兰的文明总共有 $n$ 个关键信息，编号为 $1, 2, \\ldots, n$。他们需要保留的信息是这些关键信息的一个子集 $S$。对于一个编号为 $x$ 的信息，只要 $S$ 中一个子集的编号和等于 $x$，那么他们设计的漂流瓶就可以在新宇宙将 $x$ 还原出来。\n\n艾和兰不禁想要思考，他们有多少种选择子集 $S$ 的方案，使得关键信息 $1, 2, \\ldots, n$ 均能被还原？艾和兰自然是只用 $1$ 微秒就算出了方案数的精确数值，现在他们想让你帮忙验算。由于方案数可能很大，你只需要输出方案数对 $M$ 取模的结果。\n\n## Input\n\n一行输入两个正整数 $N, M$。\n\n## Output\n\n输出一行一个整数，表示答案对 $M$ 取模的结果。\n\n[samples]\n\n## Note\n\n**【样例解释 \\#1】**\n\n总共有以下 $3$ 个集合满足条件：\n\n- $\\{ 1, 2, 3 \\}$\n- $\\{ 1, 2, 4 \\}$\n- $\\{ 1, 2, 3, 4 \\}$\n\n**【数据范围】**\n\n对于 $100 \\%$ 的数据，保证 $1 \\le N \\le 5 \\times {10}^5$，$2 \\le M \\le 1.01 \\times {10}^9$。\n\n| 测试点编号 | $N \\le$ | $M \\le$ |\n|:-:|:-:|:-:|\n| $1 \\sim 2$ | $20$ | $1.01 \\times {10}^9$ |\n| $3 \\sim 4$ | $100$ | $1.01 \\times {10}^9$ |\n| $5 \\sim 6$ | $5000$ | $1.01 \\times {10}^9$ |\n| $7$ | $3 \\times {10}^5$ | $127$ |\n| $8$ | $5 \\times {10}^5$ | $127$ |\n| $9$ | $3 \\times {10}^5$ | $1.01 \\times {10}^9$ |\n| $10$ | $5 \\times {10}^5$ | $1.01 \\times {10}^9$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8340","tags":["各省省选","2022","安徽","O2优化"],"sample_group":[["4 1000000007\n","3\n"],["10 1000000007\n","180\n"],["1000 65472\n","2136\n"],["100000 100\n","96\n"]],"created_at":"2026-03-03 11:09:25"}}