P8340 [AHOI2022] Rebuilding the Mountains and Rivers

Ai and Lan, who live in the small universe No. $998244353$, received a message from the Resetters and decided to respond to the Return Movement. They need to return most of the matter to the greater universe, leaving only a tiny amount to rebuild their civilization in the new universe. Their civilization has a total of $n$ key pieces of information, numbered $1, 2, \ldots, n$. The information they keep is a subset $S$ of these key pieces. For a piece of information numbered $x$, as long as there exists a subset of $S$ whose sum of numbers equals $x$, then the message bottle they designed can restore $x$ in the new universe. Ai and Lan wonder: how many ways are there to choose the subset $S$ so that all key information $1, 2, \ldots, n$ can be restored? Ai and Lan naturally computed the exact number of ways in just $1$ microsecond, and now they want you to help verify it. Since the number of ways may be very large, you only need to output the result modulo $M$.

One line contains two positive integers $N, M$.

Output one line with one integer, which is the answer modulo $M$.

**Sample Explanation \#1** There are in total the following $3$ sets that satisfy the condition: - $\{ 1, 2, 3 \}$ - $\{ 1, 2, 4 \}$ - $\{ 1, 2, 3, 4 \}$ **Constraints** For $100 \%$ of the testdata, it is guaranteed that $1 \le N \le 5 \times {10}^5$, $2 \le M \le 1.01 \times {10}^9$. | Test Point ID | $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$ | Translated by ChatGPT 5