시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 11 3 3 27.273%

문제

양방향 트리 T가 주어진다. 트리의 정점은 0번부터 N-1번까지 번호가 매겨져 있다.

T의 서브 트리는 T의 연결된 서브 그래프를 의미한다. 서브 트리의 크기는 포함되어 있는 정점의 개수이다.

T의 모든 서브 트리의 크기의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 105)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 T의 간선이 주어진다.

출력

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

예제 입력 1

3
0 1
0 2

예제 출력 1

10

예제 입력 2

5
0 1
1 2
1 3
1 4

예제 출력 2

52

예제 입력 3

1

예제 출력 3

1

예제 입력 4

2
0 1

예제 출력 4

4