分数: 1200 点
问题陈述
给你一个整数 N 和素数 P.
对于一棵树 N 顶点标记 1 通过 N,让 a_i 和 b_i 是端点 i第边缘 (1 \leq i \leq N-1)。另外,定义 x_j\ (1 \leq j \leq N-1) 为:
- 整数个数 i\ (1 \leq i \leq N-1) 满意 \min(a_i,b_i) \leq j \lt \max(a_i,b_i).
求模数 P,可能是 (x_1, x_2, \ldots, x_{N - 1}).
约束
- 2 \leq N \leq 500
- 10^8 \leq P \leq 10^9
- P 是质数。
输入
输入由标准输入按以下格式给出:
N P
输出
打印答案。
示例输入 1
3 998244353
示例输出 1
3
如果我们通过标签而不是边来区分顶点,则存在具有三个顶点的三棵不同的树。
对应 (x_1, x_2) 是 (1, 1), (2, 1),和 (1, 2),所以预期输出是 3 模数 P = 998244353.
示例输入 2
69 433416647
示例输出 2
243082757
求计数模数 P.