Your task is to count directed graphs with $n$ vertices (numbered with integers from $1$ to $n$), in which every vertex has an in-degree and out-degree equal to $2$.

We only count simple graphs, i.e., those that do not contain loops or multi-edges, but may simultaneously contain edges $a \to b$ and $b \to a$. Two graphs are considered different if and only if there exists at least one ordered pair of vertices $(a, b)$ such that the edge $a \to b$ exists in exactly one of these graphs.

Since the number of such graphs can be very large, it is sufficient to provide the remainder of the division of their count by a given prime number $p$.

Input

The single line of input contains two integers $n$ and $p$ ($3 \le n \le 500$; $10^8 + 7 \le p \le 10^9 + 7$; $p$ is a prime number).

Output

The output should contain a single integer representing the number of such graphs modulo $p$.

Examples

Input 1

4 1000000007

Output 1

9

Note

For $n = 4$, there are $9$ graphs that satisfy the conditions of the problem.