31499번 - 프랙탈 수열

문제

$N$개의 서로 다른 양의 정수로 구성된 수열 $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_i = y_i$이다.

만약 두 수열 $X,ドル $Y$가 같다면, 이를 $X = Y$로 표기한다.