405900: GYM102155 B Short Random Problem

There are lots of things to do on this contest besides this problem, so let's make it quick.

You are given a tree consisting of n vertices. 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 such tree.

The first line of input contains the only integer n (2 ≤ n ≤ 100), the number of vertices in the tree.

Each of the next n - 1 lines contains two integers u_i, v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) describing endpoints of i-th edge.

Output the answer as a value of a rational number modulo 10⁹ + 7.

Formally, it is guaranteed that under given constraints the expected value of diameter of such random tree is always a rational number (p and q are integer and coprime, q is positive), such that q is not divisible by 10⁹ + 7, which is a prime number (in case somebody missed it).

Output such integer a between 0 and 10⁹ + 6 that p - aq is divisible by 10⁹ + 7.

5
1 2
2 3
3 4
4 5

2

5
4 2
2 3
3 1
3 5

283333337

In the first sample case answer is 2 since each edge always belongs to the diameter adding 0.5 to diameter expected length.

In the second sample case expected length of diameter is that corresponds to value of a = 283333337 (since 101 - 60·283333337 =  - 17000000119 is divisible by 10⁹ + 7).