32300번 - 정다각형을 만들어요

문제

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

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

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

입력

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

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

출력

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

제한

힌트