Restore the Cosmos

In the universe numbered $998244353$, Ai and Lan have received a message from the Zeroers and decided to respond with the Regression Movement. They must return most of the matter to the Great Universe, keeping only a very small amount to rebuild their civilization in a new universe.

Their civilization contains $n$ key pieces of information, numbered $1,2,\ldots,n$. They need to keep a subset $S$ of these key pieces. For any information with number $x$, if there exists some sub-collection of $S$ whose indices sum to $x$, then the drift bottle they design can later restore information $x$ in the new universe.

In order to restore all key pieces $1,2,\ldots,n$, the chosen subset $S$ must have the property that for every $x \in \{1,2,\ldots,n\}$ there is some nonempty subset of $S$ whose elements sum to $x$. It is known that a necessary and sufficient condition for a sorted set $S=\{a_1,a_2,\ldots,a_k\}$ (with $a_1 < a_2 < \cdots < a_k$) to be able to represent every integer from $1$ up to \(\sum_{i=1}^k a_i\) is that:

$$a_1=1\quad\text{and}\quad a_i\le \left(\sum_{j=1}^{i-1}a_j\right)+1\text{ for }i\ge2.$$

Moreover, since only a limited amount of matter is kept, the total sum \(\sum_{a\in S}a\) must be at least $n$, so that all information $1,2,\ldots,n$ can be restored.

Your task is to count the number of subsets $S\subseteq\{1,2,\ldots,n\}$ satisfying the above condition (note that $1$ must be in $S$ and for $n\ge2$ the choice is forced to include small numbers to ensure all values can be represented) and output the count modulo $M$.

Input and Output: The input consists of two integers $n$ and $M$. The output is the number of valid choices for $S$ modulo $M$.

inputFormat

The first and only line of input contains two integers $n$ and $M$ ($1\le n\le N_{max}$, $M\ge1$), where $n$ is the number of key pieces and $M$ is the modulo.

outputFormat

Output a single integer, the number of valid subsets $S$ modulo $M$.

sample

1 10

1