405638: GYM102020 E Expectations sky-high

The holidays are coming and everyone is anxiously waiting to see the festive decorations of the Informatics Center, which will be planned by Mendes. Particularly, Mendes favorite part is preparing the christmas tree. We can see, by looking at his websites, that Mendes is very picky about the beauty of the things made by him. As for the christmas tree, he believes that its beauty is directly proportional to its size. The beauty of a christmas tree can be understood as the expected length of a random path on that tree. In mathematical terms, a tree is a connected acyclic graph. A path on a tree is the set of edges on the only simple path that connects two vertexes. The length of a path is the number of edges in it. Now, you must help Mendes to choose the best christmas tree for the Informatics Center! Your job is to calculate the expected value of the length of a random path on a given tree. The expected value of a random path on any tree can be expressed as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprimes. Your program must compute the value of $$$PQ^{-1}$$$ $$$mod$$$ $$$10^{9} + 7$$$.

On the first line, there will be an integer $$$N$$$ $$$(1 \le N \le 200000)$$$, the number of nodes on the tree. Then, $$$N-1$$$ lines follow, each one of them containing two integers $$$A$$$ and $$$B$$$ $$$(1 \le A, B \le N)$$$, representing an edge connecting the vertexes $$$A$$$ and $$$B$$$.

You must output a single line, containing the value of $$$PQ^{-1}$$$ $$$mod$$$ $$$10^{9} + 7$$$, where $$$\frac{P}{Q}$$$ expresses the value of the expected length of a random path on the given tree, and $$$Q^{-1}$$$ is the modular inverse of $$$Q$$$ modulo $$$10^{9} + 7$$$.

5
1 2
2 3
3 4
4 5

333333337

4
1 2
1 3
1 4

300000003

A random path on a tree can be seen this way: we randomly pick two vertexes (not necessarily distinct) from the tree and select the edges which are in the path that connects those two vertexes.