Ai and Lan, who live in the small universe numbered 998244353, received a message from the Returners and decided to respond to the return movement. They need to return most of their matter to the great universe, leaving only a tiny amount of matter to rebuild their civilization in the new universe.
Ai and Lan's civilization has a total of $n$ key pieces of information, numbered $1, 2, \dots, n$. The information they need to retain is a subset $S$ of these key pieces of information. For a piece of information numbered $x$, as long as the sum of the numbers in some subset of $S$ equals $x$, the drift bottle they designed can restore $x$ in the new universe.
Ai and Lan cannot help but wonder how many ways they can choose the subset $S$ such that all key pieces of information $1, 2, \dots, n$ can be restored. Ai and Lan naturally calculated the exact number of ways in just 1 microsecond, and now they want you to help verify it. Since the number of ways can be very large, you only need to output the result of the number of ways modulo $M$.
Input
A single line containing two positive integers $N, M$.
Output
Output a single integer representing the result of the answer modulo $M$.
Examples
Input 1
4 1000000007
Output 1
3
Note 1
There are a total of 3 sets that satisfy the condition: $\{1, 2, 3\}$ $\{1, 2, 4\}$ * $\{1, 2, 3, 4\}$
Input 2
10 1000000007
Output 2
180
Input 3
1000 65472
Output 3
2136
Input 4
100000 100
Output 4
96
Subtasks
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$.
| Test Case Number | $N \le$ | $M \le$ |
|---|---|---|
| 1, 2 | 20 | $1.01 \times 10^9$ |
| 3, 4 | $10^2$ | $1.01 \times 10^9$ |
| 5, 6 | 5,000 | $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$ |