D. 树的染色

内存限制:512 MiB 时间限制:1000 ms 输入文件:tree.in 输出文件:tree.out
题目类型:传统 评测方式:文本比较

题目描述

最近陈老师在整理树相关的一些问题,他遇到了这样一个问题:

有一棵 个节点无根树(无根树就是 个点 - 1条边组成的无环连通图),现在陈老师给每个节点涂上了 红色和蓝色。

因为陈老师是真的真的随机涂色,因此每个节点有 的概率被涂成红色,有的概率被涂成蓝色。

陈老师突然奇想,在树上选择一个连通块,使得这个最小连通块包含了所有的蓝色节点,那么在这个包含了所有蓝色节点的最小连通块中包含的红色节点的个数的期望是多少?

由于期望的答案是一个分数,请输出该分数 对 取余的结果。

注意:如果 , 那么满足

输入格式

输入文件 tree.in

第一行一个整数 N, 表示树上有 N 个节点

接下来 N - 1 行,表示树上的 N - 1 条边。

输出格式

输出文件 tree.out

输出一个整数表示答案

样例

样例输入 1

3
1 2
2 3

样例输出 1

125000001

样例解释 1

期望是

故输出 125000001, 因为

样例输入 2

4
1 2
2 3
3 4

样例输出 2

375000003

数据范围与提示

对于其中 的数据,满足树退化成一条链

对于其中 的数据,满足树其中一个点的度为 - 1

对于 的数据,满足