Fractal Sequence

There is a sequence $A$ of $N$ distinct positive integers. Let $B$ be the sequence obtained by sorting $A$ in ascending order. Using $B$, define a sequence $C$ of length $N$ as follows.

$c_i = \begin{cases} b_{b_i} & \text{if } 1 \le b_i \le N \\ 0 & \text{otherwise} \end{cases}$

Here, for every $i$ with $1 \le i \le N$, $b_i$ is the $i$-th element of $B$, and $c_i$ is the $i$-th element of $C$.

A sequence $A$ is called a fractal sequence if $B = C$. Given $N$ and $M$, find the number of distinct fractal sequences of length $N$, modulo $M$.

The first line contains two integers $N$ ($1 \le N \le 10^3$) and $M$ ($1 \le M \le 10^9$), separated by a space.

Print the number of distinct fractal sequences of length $N$, modulo $M$.

Two sequences $X$ and $Y$ are equal if and only if the following holds.

• $X$ and $Y$ have the same length.
• If that length is $N$, then for every $i$ with $1 \le i \le N$, the $i$-th element $x_i$ of $X$ equals the $i$-th element $y_i$ of $Y$.

If two sequences $X$ and $Y$ are equal, this is written as $X = Y$.