Gates is a super rich man . Because of the influence of COVID-19 , he had to do enough protection .

To keep himself away from the virus , he formulated strict protective measures .

Gates has exactly servants , he numbers them to (Gates is number ) , and edges satisfies that and may contact with each other , if one of them is infected with the virus , then the other one has probability of being infected .

We promise that the edges from a tree , Gates is the root .

The level of a person is defined as the depth of him on the tree (Gates's level is always 1) .

Now we know for the person , he has probability of infecting the virus from the outside world (At the beginning) .

We define the disaster value as the lowest level of the person who infected of the virus . ( If there are no one infected , the disaster value is 0 ) .

Now please help Gates to calculate what's the expectation of the disaster value ?

The first line has an integer  .

The next  lines contains  pair of integers , the  pair describes  .

Then  lines , each line contains  integers   described before .

If the answer is  （simplest fraction），print  .

3
0 1
0 1
1 1
1 2 1 2
2 3 1 2

250000004

The probability of infection (1,2,3) is  .

The probability of infection (2,3) is  .

The probability of infection (3) is  .

So the answer is  .