Short Random Problem

Time limit6sMemory limit512 MB

Summary

Given a tree whose edge lengths are independent uniform random reals in [0, 1], find the expected diameter modulo 10^9+7.

Level: Hard9 of 10
Topics: Tree, Probability, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

This contest has many other problems besides this one, so let us keep it short.

You are given a tree with $n$ vertices. The length of each edge is a real number chosen independently and uniformly at random between $0$ and $1$ . Find the expected value of the diameter of this tree.

Input

The first line contains one integer $n$ ( $2 \leq n \leq 100$ ), the number of vertices.

Each of the next $n-1$ lines contains two integers $u_i$ , $v_i$ ( $1 \leq u_i, v_i \leq n$ , $u_i \neq v_i$ ), the endpoints of the $i$ -th edge.

Output

Print the answer modulo $10^9 + 7$ . The expected diameter is a rational number $\frac{p}{q}$ with $p$ and $q$ coprime, and $q$ is not divisible by $10^9 + 7$ . Print the integer $a$ between $0$ and $10^9 + 6$ such that $p - aq$ is divisible by $10^9 + 7$ .

Examples2

Example 1
Input
```
5
1 2
2 3
3 4
4 5
```
Expected output
```
2
```
Example 2
Input
```
5
4 2
2 3
3 1
3 5
```
Expected output
```
283333337
```