/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1600 点
問題文
偶数 N および素数 M が与えられます。
1 から N までの番号が付いた N 頂点からなる単純連結無向グラフ G のうち、以下の条件を満たすものの個数を M で割った余りを求めてください。
- G の任意の全域木 T に対し、T 上の完全マッチングが存在する。
グラフの完全マッチングとは？
グラフ G に対し、 G の辺からなる集合 E であって、グラフ上のすべての頂点 v に対し、 v を端点とする辺がちょうど 1 つ E に含まれるようなものを G 上の完全マッチングとよびます。制約
- 2 \leq N \leq 500
- 10^8 \leq M \leq 10^9
- N は偶数
- M は素数
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
4 998244353
出力例 1
15
例えば下図で示された 2 つのグラフについて、左側のグラフは条件を満たします。一方、右側のグラフは赤い太線で示された 3 辺からなる全域木上には完全マッチングが存在しないため、条件を満たしません。
入力例 2
10 998244353
出力例 2
128792160
入力例 3
300 923223991
出力例 3
359143490
Score : 1600 points
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.
Sample Input 1
4 998244353
Sample Output 1
15
For example, among the two graphs shown in the figure below, the graph on the left satisfies the condition. On the other hand, the graph on the right does not because there is no perfect matching in the spanning tree with the three edges shown in bold red.
Sample Input 2
10 998244353
Sample Output 2
128792160
Sample Input 3
300 923223991
Sample Output 3
359143490