Purrs Across the Branches
There is one cat on each vertex of an undirected tree. The cats wake one by one in an order chosen uniformly at random from all possible orders.
When the cat at vertex wakes, consider the connected components that remain after removing and all edges incident to it. Each such component is called a branch of .
A branch is calling if it contains at least one cat that woke before the cat at . If exactly branches are calling, the cat at receives
purr tokens. Thus, it receives one token for every unordered pair of calling branches.
The total score is the sum of the tokens received by all cats. Determine the expected value of modulo .
Input
The first line contains an integer (), the number of vertices in the tree.
The next lines describe the edges. The -th of these lines contains two integers and (, ), indicating an undirected edge between vertices and .
Output
Let the expected total score be , where is in lowest terms. Print the integer
Samples
Sample 1
Input
1
Output
0
The only cat has no branches, so the total score is always .
Sample 2
Input
3 1 2 2 3
Output
332748118
Only the cat at vertex can score. It receives one token exactly when both endpoint cats wake before it, which occurs with probability .
Sample 3
Input
4 1 2 2 3 3 4
Output
831870295
Only vertices and can score. Each has expected score , so the expected total is , represented modulo .