Sum of subtree sizes

Time limit2sMemory limit512 MB

Summary

Count all connected subgraphs of a tree and output the sum of their vertex counts modulo 1e9+7.

Level: Medium6 of 10
Topics: Tree, Dynamic programming, Combinatorics, DFS
Solved: No attempts yet

Problem

You are given an undirected tree $T$ . Its vertices are numbered from $0$ to $N-1$ .

A subtree of $T$ is a connected subgraph of $T$ that contains at least one vertex. The size of a subtree is the number of vertices in it.

Write a program that computes the sum of the sizes of all subtrees of $T$ .

Input

The first line contains the number of vertices $N$ ( $1 \le N \le 10^5$ ).

Each of the next $N-1$ lines contains one edge of the tree, given as the numbers $u$ and $v$ of the two vertices it joins ( $0 \le u, v \le N-1$ , $u \ne v$ ).

The given edges always form a tree.

Output

Print the sum of the sizes of all subtrees of $T$ modulo 1,000,000,007.

Examples4

Example 1
Input
```
3
0 1
0 2
```
Expected output
```
10
```
Example 2
Input
```
5
0 1
1 2
1 3
1 4
```
Expected output
```
52
```
Example 3
Input
```
1
```
Expected output
```
1
```
Example 4
Input
```
2
0 1
```
Expected output
```
4
```