munte

Task

A permutation of order $N$ is called a mountain permutation if and only if for every $i$, $1 \leq i \leq N$, with $i$ even, the condition $v[i-1]>v[i]<v[i+1]$ holds. If $i=N$, only the condition $v[i-1]>v[i]$ needs to hold.

For example, the permutation of order 5 $[2, 1, 4, 3, 5]$ is a mountain permutation because $2>1<4$ and $4>3<5$, but the permutation of order 5 $[2, 1, 5, 4, 3]$ is not a mountain permutation because $5>4>3$, so for $i=4$ the condition is not satisfied.

A permutation of order $N$ is a sequence of $N$ elements that contains all elements from $1$ to $N$ in any order. For example, the sequence $[1, 4, 5, 2, 3]$ is a permutation of order $5$, but the sequences $[1, 3, 2, 3, 5]$ and $[1, 2, 3, 5, 6]$ are not permutations of order $5$.

Given a number $N$, find the number of mountain permutations of order $i$, $1 \leq i \leq N$. Since the answer can be very large, only the remainder of the answer divided by another given number $M$ is requested.

Input data

The first line contains the natural numbers $N$, representing the order number for which you need to find the permutations, and $M$, the modulo for the answer.

Output data

The first line contains the result modulo $M$.

Constraints and clarifications

• $1 \leq N \leq 5000$
• $1 \leq M \leq 10^9$
• $M$ is prime
• $M > N$

Example

stdin

5 19

stdout

6

Explanation

The number of mountain permutations of order $\leq 5$ is $25$. Two of these permutations are $[4, 1, 3, 2]$ and $[3, 1, 2]$.