说明

小 A 和 小 B 在树上玩游戏。

给定一棵有根树 $T$，以 $1$ 为根。

小 B 从根节点出发。每一回合，他可以选择走向当前节点的一个儿子。小 B 不知道树的结构，即他只知道当前节点的儿子集合。

小 A 从任意叶子节点出发，每一回合，小 A 可以移动到任意一个叶子节点。小 A 知道树的结构。小 A 知道小 B 从根节点出发，除此之外在游戏过程中他不知道小 B 所在节点。每一回合开始前，小 A 也可以使用技能得知小 B 所在的位置。

现在双方开始游戏。每一回合，流程如下：

• 小 A 选择是否使用技能得知当前小 B 的位置；

• 双方同时开始移动；

• 如果小 B 位于叶子节点，那么：如果小 A 也位于该叶子节点，小 A 获胜；否则，小 B 获胜。

小 A 的目标是在最大化获胜概率的前提下最小化使用技能的次数，小 B 的目标是最大化获胜概率。

小 A 和小 B 是绝顶聪明的，并且他们均使用最优策略。

小 A 和小 B 均知道对方的情况和游戏规则，并且他们也知道对方知道自己的情况和游戏规则，以此类推。也就是说，游戏规则和双方的情况是双方的公共知识。

求小 A 使用技能的期望次数，对 $10^9+7$ 取模。

提示：如果你对纳什均衡的相关知识并不了解，你可以认为小 B 每次会等概率随机走向一个儿子节点。

输入格式

第一行，输入一个正整数 $n$，表示树的节点个数。

接下来的 $n-1$ 行，每一行读入两个正整数 $u,v$，表示树上的一条边 $(u,v)$。

输出格式

输出一行一个整数，表示小 A 使用技能的期望次数对 $10^9+7$ 取模的结果。

6
1 2
1 3
2 4
2 5
3 6

1

提示

样例解释

小 A 的一种最优策略是在第二回合开始使用技能查看小 B 的位置，确定小 B 在 $2$ 号节点或者 $3$ 号节点。如果小 B 在 $2$ 号节点，那么小 A 在 $4,5$ 号节点中随机一个等待，获胜概率为 $\frac{1}{2}$，如果小 B 在 $3$ 号节点，那么小 A 在 $6$ 号节点等待，期望使用技能次数为 $1$。可以证明不存在更优的策略。

数据范围

本题采用捆绑测试。

特殊性质 A：$\forall i\in[1,n),u_i=1$。

特殊性质 B：$\forall i\in[1,n),u_i=i,v_i=i+1$。

对于所有数据，保证 $2\le n\le10^6$ 且给出的是一棵树。