시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB126444144.565%

문제

호반우는 $1$번부터 $N$번까지 번호가 매겨진 정점이 $N$개인 트리에서 정다각형을 찾으려고 한다.

트리에서의 정다각형이란 서로 다른 $2$개 이상의 정점을 선택하였을 때 선택한 정점 모두와 거리가 같은 정점이 단 하나만 존재한다면 선택한 정점의 집합을 정다각형이라 부른다. 두 정점 사이의 거리란, 한 정점과 다른 정점을 잇는 유일한 단순 경로 위의 간선의 개수로 정의한다.

정다각형을 하나하나 세고 있는 호반우를 위해 트리에서 서로 다른 정다각형이 몇 개나 있는지 알려주자.

입력

첫째 줄에 양의 정수 $N$이 주어진다. $(1 \leq N \leq 2\,000)$

둘째 줄부터 $N - 1$개의 줄에 걸쳐 트리의 각 간선이 잇는 두 정점의 번호 $u, v$가 공백을 두고 주어진다. $(1 \leq u < v \leq N)$

출력

첫째 줄에 주어진 트리에서 정다각형의 개수를 출력한다. 단, 수가 매우 커질 수 있으므로 $10^{9} + 7$로 나눈 나머지를 출력한다.

예제 입력 1

5
1 3
3 4
3 5
2 3

예제 출력 1

1

예제 입력 2

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

예제 출력 2

10

출처

University > 경북대학교 > 2024 Goricon D번