D. Dog
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Somewhere in the town of Lean, a highly intelligent Corgi named Dog assists her owner in computer science research. They are currently dabbling in proof verification, where the structure of a proof can be represented as a rooted tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. In this tree, we call root node $$$1$$$ the "goal" and all other nodes as "subgoals" derived from the goal. There is an edge from node $$$a$$$ to node $$$b$$$ if $$$b$$$ is directly derived from $$$a$$$. This time, Dog's owner is working on a peculiar proof.

Example: A proof structure as a rooted tree

This proof is composed of multiple steps.

During a single step of verification, only one leaf node can be solved, and any valid leaf node can be chosen. A leaf node $$$s$$$ that is solved is removed from the tree and the following changes occur:

  • If $$$s$$$ was connected directly to the root node, then no more nodes are generated.
  • Otherwise, among the ancestors of $$$s$$$ , find the one that is directly beneath the root node. The verifier generates two more copies of that ancestor, along with all its children, and connects both of these to the root node.
After the gray node is removed, two copies of the ancestor node and its children are appended to the root node in purple.

Her owner comments that the proof seems endless. However, Dog knows that a proof terminates when there are no more subgoals to solve, i.e. when the tree is reduced to the single root node. In order to ease the burden of her owner's work, Dog wants to figure out the minimum number of steps needed to terminate the proof given the current proof structure. Please help her compute this modulo $$$10^9+7$$$.

Input

The input is a rooted tree describing the current proof structure.

The first line contains an integer $$$n\:(1 \leq n \leq 10^5)$$$.

The next $$$n-1$$$ lines contain the edges of the tree. The $$$i$$$-$$$th$$$ line contains integers $$$a_i, b_i\: (1 \leq a_i, b_i\leq n; a_i\neq b_i)$$$ — the vertices connected by an edge of the tree.

Output

A single integer representing the minimum number of steps needed to terminate the proof, modulo $$$10^9+7$$$.

Examples
Input
5
1 2
2 3
2 4
1 5
Output
14
Input
7
1 2
2 3
2 4
4 5
4 6
1 7
Output
122
Note

In the first test case, we can do the following,

On step 1, we remove the grey leaf node with no change to the program.

On step 2, we create two purple copies of the subgraph after removing the grey leaf node.

For steps 3-13, we continue choosing a node to remove, and creating two copies of the remaining subgraph.

On step 14, we remove the last leaf node, successfully reaching termination.