/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正整数 N, M が与えられます。
頂点に 1, \dots, N の番号が付けられた N 頂点の単純連結無向グラフであって、以下の条件を満たすものの総数を M で割った余りを求めてください。
- 全ての u = 2, \dots, N-1 について、頂点 1 から頂点 u までの最短距離は、頂点 1 から頂点 N までの最短距離より真に小さい。
ただし、頂点 u から頂点 v までの最短距離とは、頂点 u, v を結ぶ単純パスに含まれる辺の本数の最小値を指します。
また、2 つのグラフが異なるとは、ある 2 頂点 u, v が存在して、これらの頂点を結ぶ辺が一方のグラフにのみ存在することを指します。
制約
- 3 \leq N \leq 500
- 10^8 \leq M \leq 10^9
- N, M は整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
4 1000000000
出力例 1
8
以下の 8 通りが条件を満たします。
入力例 2
3 100000000
出力例 2
1
入力例 3
500 987654321
出力例 3
610860515
M で割った余りを求めることに注意してください。
Score : 600 points
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.