Problem Description

In the universe numbered $998244353$, Ai and Lan receive a message from the Zero-State and decide to respond to the movement of returning. They need to return most of their matter to the greater universe, leaving only a minimal amount to rebuild their civilization in the new universe.

Ai and Lan's civilization has a total of $n$ critical pieces of information, numbered $1, 2, \ldots, n$. The subset $S$ of these pieces of information that they need to retain must be such that for any piece of information numbered $x$, there exists a subset of $S$ whose sum of numbers equals $x$. This ensures that the bottle they design can restore $x$ in the new universe.

Ai and Lan wonder how many ways they can choose the subset $S$ such that all pieces of information from $1$ to $n$ can be restored. Naturally, they calculate the exact number of schemes in just $1$ microsecond, and now they want you to verify the calculation. Since the number of schemes might be very large, you only need to output the result modulo $M$.

Input Format

A single line containing two positive integers $N, M$.

Output Format

Output a single integer, which is the result modulo $M$.

Sample Input and Output

Sample Input #1

4 1000000007

Sample Output #1

3

Sample Input #2

10 1000000007

Sample Output #2

180

Sample Input #3

1000 65472

Sample Output #3

2136

Sample Input #4

100000 100

Sample Output #4

96

Notes/Hints

[Sample Explanation #1]

There are a total of $3$ sets that meet the conditions:

• $\{1, 2, 3\}$
• $\{1, 2, 4\}$
• $\{1, 2, 3, 4\}$

[Data Range]

For $100\%$ of the data, it is guaranteed that $1 \le N \le 5 \times 10^5$ and $2 \le M \le 1.01 \times 10^9$.

见题面 Input 部分

见题面 Output 部分