405900: GYM102155 B Short Random Problem

Memory Limit:512 MB Time Limit:6 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Short Random Problemtime limit per test6 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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 ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi) describing endpoints of i-th edge.

Output

Output the answer as a value of a rational number modulo 109 + 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 109 + 7, which is a prime number (in case somebody missed it).

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

ExamplesInput
5
1 2
2 3
3 4
4 5
Output
2
Input
5
4 2
2 3
3 1
3 5
Output
283333337
Note

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 109 + 7).

加入题单

上一题 下一题 算法标签: