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.

Input

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

Output

Print the answer.

Constraints

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

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.

见题面 Input 部分

见题面 Output 部分