/ 
Time Limit: 4.5 sec / Memory Limit: 2048 MiB
配点 : 1200 点
問題文
整数 N と素数 P が与えられます。
頂点に 1 から N までの番号がついた N 頂点の木に対し、i\ (1 \leq i \leq N-1) 番目の辺が結ぶ頂点の番号を a_i, b_i とします。また、x_j\ (1 \leq j \leq N-1) を次のように定めます。
- \min(a_i,b_i) \leq j \lt \max(a_i,b_i) を満たす整数 i\ (1 \leq i \leq N-1) の個数
(x_1,x_2, \ldots,x_{N-1}) としてあり得るものの個数を P で割った余りを求めてください。
制約
- 2 \leq N \leq 500
- 10^8 \leq P \leq 10^9
- P は素数
入力
入力は以下の形式で標準入力から与えられる。
N P
出力
答えを出力せよ。
入力例 1
3 998244353
出力例 1
3
3 頂点の木は、頂点同士は番号で区別して辺同士は区別しないことにすると 3 個あります。
それぞれに対応する (x_1,x_2) は (1,1),(2,1),(1,2) であり、期待される出力は 3 を P=998244353 で割った余りになります。
入力例 2
69 433416647
出力例 2
243082757
P で割った余りを求めてください。
Score : 1200 points
Problem Statement
You are given an integer N and a prime P.
For a tree with N vertices labeled 1 through N, let a_i and b_i be the endpoints of the i-th edge (1 \leq i \leq N-1). Also, define x_j\ (1 \leq j \leq N-1) as:
- The number of integers i\ (1 \leq i \leq N-1) satisfying \min(a_i,b_i) \leq j \lt \max(a_i,b_i).
Find the number, modulo P, of sequences that could be (x_1, x_2, \ldots, x_{N - 1}).
Constraints
- 2 \leq N \leq 500
- 10^8 \leq P \leq 10^9
- P is prime.
Input
The input is given from Standard Input in the following format:
N P
Output
Print the answer.
Sample Input 1
3 998244353
Sample Output 1
3
There are three different trees with three vertices, if we distinguish the vertices by their labels but not the edges.
The corresponding (x_1, x_2) are (1, 1), (2, 1), and (1, 2), so the expected output is 3 modulo P = 998244353.
Sample Input 2
69 433416647
Sample Output 2
243082757
Find the count modulo P.