Problem Statement

You are given an even number $N$ and a prime number $M$.

Find the number, modulo $M$, of simple connected undirected graphs $G$ with $N$ vertices numbered $1$ to $N$ that satisfy the following condition:

• For every spanning tree $T$ of $G$, there is a perfect matching in $T$.

What is a perfect matching in a graph? For a graph $G$, a set of edges $E$ from $G$ is called a perfect matching in $G$ if, for every vertex $v$ in the graph, $E$ contains exactly one edge with $v$ as an endpoint.

Constraints

• $2 \leq N \leq 500$
• $10^8 \leq M \leq 10^9$
• $N$ is even.
• $M$ is prime.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M

Output

Print the answer.