## Magical Tower Sequences

View as PDF

Points: 1
Time limit: 2.0s
Memory limit: 256M

Problem types

Yusuf is a mighty wizard and he gets his power from magical tower sequences. A magical tower sequence is a sequence of $$n$$ magical towers in a row.

Let's assume that the height of the $$i$$-th tower is $$A_i$$. Let's say that tower $$j$$ is visible from tower $$i$$ if tower $$j$$ is strictly higher than all towers between tower $$i$$ and tower $$j$$ (not including the $$i$$-th tower). More formally, let $$S$$ be the range of all towers between $$i$$-th and $$j$$-th tower. This means that $$S=[i+1, j-1]$$ if $$j>i$$, and $$S=[j+1, i-1]$$ otherwise. The $$j$$-th tower is visible from the tower $$i$$ if $$\forall_{k \in S} A_j>A_k$$.

Let $$B_i$$ be the number of towers visible from tower $$i$$ (not including tower $$i$$). Yusuf calls a sequence of towers lucky if $$A_i=B_i$$ for all $$i$$. Yusuf wants you to find the number of lucky sequences of $$n$$ towers modulo prime number $$m$$.

#### Input

The first line contains 2 integers $$n$$ and $$m$$.

• $$2 \le n \le 1000$$,
• $$10^7 \le m \le 10^9$$, $$m$$ is prime.

#### Output

Print one number, the number of lucky sequences of $$n$$ towers modulo $$m$$.

#### Example

Input:

7 47774477

Output:

3

#### Explanation

Lucky sequences are $$[1,2,2,2,2,2,1]$$, $$[2,2,3,2,3,2,2]$$, $$[2,3,2,4,2,3,2]$$.