A6591. 「AHOI2022」山河重整

生活在 $998244353$ 号小宇宙的艾和兰收到了归零者的讯息，决定响应回归运动。他们需要把大部分的物质归还给大宇宙，只留下极少的物质用于在新宇宙重建自己的文明。

艾和兰的文明总共有 $n$ 个关键信息，编号为 $1, 2, \dots, n$。他们需要保留的信息是这些关键信息的一个子集 $S$。对于一个编号为 $x$ 的信息，只要 $S$ 中一些关键信息的总和等于 $x$，那么他们设计的漂流瓶就可以在新宇宙将 $x$ 还原出来。

艾和兰不禁想要思考，他们有多少种选择子集 $S$ 的方案，使得关键信息 $1,2,\dots, n$ 均能被还原？艾和兰自然是只用 $1$ 微秒就算出了方案数的精确数值，现在他们想让你帮忙验算。由于方案数可能很大，你只需要输出方案数对 $M$ 取模的结果。

一行输入两个正整数 $N$、$M$。

输出一行一个整数，表示答案对 $M$ 取模的结果。

对于 $100\%$ 的数据，保证 $1\leq N\leq 5\times 10^5$，$2\leq M\leq 1.01\times 10^9$。


| 测试点编号 | $N \le$ | $M \le$ |
|:-:|:-:|:-:|
| $1 \sim 2$ | $20$ | $1.01 \times {10}^9$ |
| $3 \sim 4$ | $100$ | $1.01 \times {10}^9$ |
| $5 \sim 6$ | $5000$ | $1.01 \times {10}^9$ |
| $7$ | $3 \times {10}^5$ | $127$ |
| $8$ | $5 \times {10}^5$ | $127$ |
| $9$ | $3 \times {10}^5$ | $1.01 \times {10}^9$ |
| $10$ | $5 \times {10}^5$ | $1.01 \times {10}^9$ |