시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 7 6 6 85.714%

문제

숭고한 연합에서는 알고리즘 마라톤 대회를 개최하기 위해 적당한 장소를 선정했다. 이 장소는 N개의 교차로와 N-1개의 양방향 도로들로 이루어져 있고, 모든 서로 다른 교차로 쌍 사이에 정확히 하나의 경로가 존재한다. (다시 말해, 이 장소는 트리 구조이다.)

명색이 알고리즘 마라톤이므로 주자들이 머릿속으로 최단경로 알고리즘을 돌리면서 달릴 수 있도록 다양한 코스가 존재하면 좋을 것이다. 따라서 서로 다른 두 교차로를 잘 골라서 각각 시작 교차로와 끝 교차로로 선정했을 때, 숭실대/고려대/한양대 세 학교가 시작 교차로에서 끝 교차로로 가는 겹치지 않는 세 개의 경로를 정할 수 있도록 하는 것이 목표이다. 어떤 두 경로가 겹치지 않으려면 시작 교차로와 끝 교차로를 제외하고는 공유하는 교차로가 없어야 한다.

목표를 달성할 수 있게 장소에 정확히 2개의 도로를 추가할 것이다. 어떤 도로들을 추가할지 정하는 방법이 몇 가지나 있는지 알려주자. 방법의 수가 너무 많을 수 있으므로 109+7로 나눈 나머지를 출력하라. 도로 추가 이후 두 교차로 사이에는 최대 하나의 도로만 존재해야 하고, 어떤 도로도 양 끝 교차로가 같아서는 안 된다. (다시 말해, 단순 그래프이어야 한다.)

방법 1의 경우: 2를 시작 교차로로, 3을 끝 교차로로 정하면 3개의 서로 겹치지 않는 경로가 생긴다.

방법 2의 경우: 1을 시작 교차로로, 2를 끝 교차로로 정하면 3개의 서로 겹치지 않는 경로가 생긴다.

방법 3의 경우: 2를 시작 교차로로, 4를 끝 교차로로 정하면 3개의 서로 겹치지 않는 경로가 생긴다.

따라서 주어진 트리에서 가능한 방법은 3가지이고 정답은 3이 된다.

입력

첫 번째 줄에 교차로의 개수 N이 주어진다. (4 ≤ N ≤ 500,000)

두 번째 줄부터 N-1개의 줄에 걸쳐 각 도로가 연결하는 두 교차로의 번호 a,b가 공백으로 구분되어 주어진다. (1 ≤ a,b ≤ N)

주어지는 입력은 트리임이 보장된다.

출력

목표를 달성할 수 있게 도로 2개를 정하는 방법의 수를 109+7로 나눈 나머지를 출력한다.

예제 입력 1

4
1 2
2 3
2 4

예제 출력 1

3

예제 입력 2

5
1 2
2 3
3 4
4 5

예제 출력 2

14

예제 입력 3

7
1 2
1 3
2 4
2 5
3 6
3 7

예제 출력 3

90

예제 입력 4

11
1 2
2 3
2 4
2 5
5 6
5 7
7 8
7 9
7 10
7 11

예제 출력 4

716