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]\).