时间限制:2 秒,空间限制:512 MB。
题面描述
给定 N,V,求 ∑T是一棵$N$个点的有标号无根树 f(T) 对 P 取模后的结果。
对于一棵 N 个点的有标号无根树 T,定义 f(T) 为合法的给每个节点赋权的方案数,令 i 号点的权值 ai,定义一个赋权方案合法,当且仅当对于所有树上的所有非空连通块 S,都满足:
mex({ai∣i∈S})=min
此处定义 \text{mex}(E) 为 E 集合内未出现过的最小非负整数,\min(E) 为 E 集合内元素的最小值。特别地,定义 \text{mex}(\emptyset) = 0, \min(\emptyset) = V + 1。
输入格式
一行输入三个数 N, V, P。
输出格式
一行输出一个数,表示 \sum_{T} 是一棵 N 个点的有标号无根树 f(T) 对 P 取模后的结果。
测试样例
样例 1
输入
5 3 998244353
输出
2280
样例 2, 3, 4
见下发文件。
数据范围
对于全部数据,满足:
1 \leq N \leq 150, \quad 1 \leq V \leq 10^9, \quad 3 \leq P \leq 1.01 \times 10^9
子任务 | 分值 | N\leq |
---|---|---|
1 | 5 | 4 |
2 | 15 | 6 |
3 | 30 | 50 |
4 | 50 | 150 |