Problem Description

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$.

Input Format

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

Output Format

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

4 1000000007

3

10 1000000007

180

1000 65472

2136

100000 100

96

Hint

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$.

Translated by ChatGPT 5