201 패턴을 피하는 상승 수열

음이 아닌 정수로 이루어진 수열 $\langle a_1, a_2, \ldots, a_n \rangle$을 생각하자. 수열의 상승은 인접한 두 원소 중에서 인덱스가 큰 쪽의 값이 더 큰 쌍이다. 예를 들어 수열 $\langle 0, 2, 3, 1, 0 \rangle$에는 두 개의 상승이 있다. $a_1 = 0$에서 $a_2 = 2$로 가는 것과 $a_2 = 2$에서 $a_3 = 3$으로 가는 것이다. 수열의 처음 $k$개 원소에 있는 상승의 개수를 $A_k$라고 쓰자. 위의 예에서 $A_1 = 0$, $A_2 = 1$, $A_3 = 2$, $A_4 = 2$, $A_5 = 2$이다.

수열 $a$가 상승 수열이라는 것은 $a_1 = 0$이고, 모든 $i \ge 2$에 대해 부등식 $a_i \le A_{i-1} + 1$이 성립한다는 뜻이다. 예를 들어 수열 $\langle 0, 2, 3, 1, 0 \rangle$은 $a_2 = 2$이고 $A_1 = 0$이므로 상승 수열이 아니다. 반면 수열 $\langle 0, 1, 0, 2, 3 \rangle$은 $A_1 = 0$, $A_2 = 1$, $A_3 = 1$, $A_4 = 2$이므로 상승 수열이다.

음이 아닌 정수로 이루어진 수열 $\langle a_1, a_2, \ldots, a_n \rangle$이 201 패턴을 피한다는 것은 $i < j < k$이고 $a_j < a_k < a_i$인 $i$, $j$, $k$가 존재하지 않는다는 뜻이다. 예를 들어 수열 $\langle 0, 1, 0, 2, 3 \rangle$은 201 패턴을 피하지만, $\langle 0, 1, 2, 3, 1, 0, 2 \rangle$는 $i = 4$, $j = 6$, $k = 7$에 대해 $a_j = 0 < a_k = 2 < a_i = 3$이므로 201 패턴을 피하지 않는다.

두 정수 $n$과 $p$가 주어진다. 201 패턴을 피하는 길이 $n$의 상승 수열의 개수를 구하여 $p$로 나눈 나머지를 출력하자.

입력은 한 줄이며 두 정수 $n$과 $p$가 주어진다. ($1 \le n \le 500$; $2 \le p \le 10^9 + 123$; $p$는 소수)

201 패턴을 피하는 길이 $n$의 상승 수열의 개수를 $p$로 나눈 나머지를 한 줄에 출력한다.

첫 번째 예제에서 201 패턴을 피하는 길이 3의 상승 수열은 다섯 개이다. $\langle 0, 0, 0 \rangle$, $\langle 0, 0, 1 \rangle$, $\langle 0, 1, 0 \rangle$, $\langle 0, 1, 1 \rangle$, $\langle 0, 1, 2 \rangle$.

두 번째 예제에서 길이 5의 상승 수열은 53개이며, $\langle 0, 1, 2, 0, 1 \rangle$을 제외한 나머지 모두가 201 패턴을 피한다.