Problem Statement

There is a directed tree with $N$ vertices, and the $i$-th edge goes from vertex $A_i$ to vertex $B_i$. Also, each vertex other than the root has one directed edge coming from its parent.
Define the function $f(a,b)$ as follows.
$f(a,b)=$ the length of the path from vertex $a$ to vertex $b$ (the number of edges traversed when going from vertex $a$ to vertex $b$)
However, if no path exists, let $f(a,b)=0$. Also, let $f(a,a)=0$.
Find $\displaystyle \sum_{i=1}^n \sum_{j=1}^n f(i,j)$. Since the answer can be large, find the remainder when it is divided by $10^9+7 $.

Notes

It has been confirmed that a solution passes with PyPy3, but this has not been confirmed with Python.

Input

$N$
$A_1\ B_1$
$A_2\ B_2$
:
$A_{N-1}\ B_{N-1}$

The constraints are as follows.
・$3 \le N \le 10^6$
・If $i \neq j $, then $(A_i,B_i) \neq (A_j,B_j)$
・$1 \le A_i,B_i \le N (1 \le i \le N - 1)$
・The given graph is a directed tree

Output

Output the answer. Print a newline at the end.

Sample

3
1 2
1 3

2

5
2 1
1 3
1 4
3 5

13