프랙탈 수열

서로 다른 양의 정수 $N$개로 이루어진 수열 $A$가 있다. $A$를 오름차순으로 정렬한 수열을 $B$라 하자. $B$로부터 길이 $N$인 수열 $C$를 다음과 같이 정의한다.

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

여기서 $1 \le i \le N$인 모든 $i$에 대해 $b_i$는 $B$의 $i$번째 원소를, $c_i$는 $C$의 $i$번째 원소를 나타낸다.

$B = C$가 되도록 하는 수열 $A$를 프랙탈 수열이라고 하자. $N$과 $M$이 주어졌을 때, 길이가 $N$인 서로 다른 프랙탈 수열의 개수를 $M$으로 나눈 나머지를 구하라.

첫 번째 줄에 두 정수 $N$ ($1 \le N \le 10^3$)과 $M$ ($1 \le M \le 10^9$)이 공백으로 구분되어 주어진다.

길이가 $N$인 서로 다른 프랙탈 수열의 개수를 $M$으로 나눈 나머지를 출력한다.

두 수열 $X$, $Y$가 같기 위한 필요충분조건은 다음과 같다.

• $X$의 길이와 $Y$의 길이가 같다.
• 그 길이를 $N$이라 할 때, $1 \le i \le N$인 모든 $i$에 대해 $X$의 $i$번째 원소 $x_i$와 $Y$의 $i$번째 원소 $y_i$가 같다.

두 수열 $X$, $Y$가 같다면 $X = Y$로 표기한다.