Problem Statement

You are given positive integers $N$ and $M$.
Find the number, modulo $M$, of simple connected undirected graphs with $N$ vertices numbered $1, \\dots, N$ that satisfy the following condition.

• For every $u = 2, \\dots, N-1$, the shortest distance from vertex $1$ to vertex $u$ is strictly smaller than the shortest distance from vertex $1$ to vertex $N$.

Here, the shortest distance from vertex $u$ to vertex $v$ is the minimum number of edges in a simple path connecting vertices $u$ and $v$.
Two graphs are considered different if and only if there are two vertices $u$ and $v$ that are connected by an edge in exactly one of those graphs.

Constraints

• $3 \\leq N \\leq 500$
• $10^8 \\leq M \\leq 10^9$
• $N$ and $M$ are integers.

Input

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

$N$ $M$

Output

Print the answer.

Sample Input 1

4 1000000000

Sample Output 1

8

The following eight graphs satisfy the condition.

Sample Input 2

3 100000000

Sample Output 2

1

Sample Input 3

500 987654321

Sample Output 3

610860515

Be sure to find the number modulo $M$.