#P17881. Domain Compression
Domain Compression
Gojo 有一棵包含 个顶点的树,顶点编号为 。他可以进行如下操作:
- 选择一个尚未被删除的顶点 。
- 对于当前图中与 相邻的每一对不同顶点 ,如果 之间还没有边,就添加一条连接它们的无向边。
- 删除顶点 以及所有与它相连的边。
对每个 ,考虑所有恰好进行 次操作的方式。每种方式由依次选择的 个不同顶点确定,因此一共有 种方式。
对于每个 ,求所有这些方式执行结束后,剩余图的边数之和,并对 取模。
注意:不同的顶点删除顺序计为不同的方式,即使它们得到相同的最终图。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,表示原树的一条边。
输出格式
输出 个整数,第 个整数是恰好进行 次操作时所求的边数之和,对 取模。
数据范围
,。输入保证构成一棵树。
样例 1
5
1 2
2 3
3 5
3 4
16 44 60 0 0
样例 2
8
1 2
2 3
2 4
4 5
4 7
7 8
6 7
51 316 1596 6120 15720 20160 0 0