서브 트리의 크기 합

트리의 모든 연결 부분그래프를 세고, 각 부분그래프의 정점 수 합을 1e9+7로 나눈 나머지를 구한다.

보통6트리동적 계획법조합론DFS아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

양방향 트리 TT가 주어진다. 트리의 정점에는 00번부터 N1N-1번까지 번호가 붙어 있다.

TT의 서브 트리는 정점을 하나 이상 포함하는 TT의 연결된 부분 그래프를 뜻한다. 서브 트리의 크기는 그 안에 들어 있는 정점의 개수이다.

TT의 모든 서브 트리의 크기를 더한 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 NN이 주어진다. (1N1051 \le N \le 10^5)

다음 N1N-1개의 줄에 트리의 간선이 한 줄에 하나씩 주어진다. 각 줄에는 간선으로 이어진 두 정점의 번호 uuvv가 주어진다. (0u,vN10 \le u, v \le N-1, uvu \ne v)

주어지는 간선은 항상 트리를 이룬다.

출력

첫째 줄에 모든 서브 트리의 크기의 합을 1,000,000,007로 나눈 나머지를 출력한다.