혼란도

맬나르 씨는 여름 동안 행선지를 무작위로 정해 비행기로 세계를 여행하기로 했다. 얼마 뒤 그는 낯선 나라의 수도에 도착했는데, 그곳의 도로는 삼각분할을 떠올리게 했다. 정확히 말하면, 이 도시에는 1번부터 $N$번까지 번호가 붙은 $N$개의 볼거리가 있고, 이들은 $2N - 3$개의 도로로 이어져 있다. 지점 $1, 2, \dots , N$은 이 순서대로 연결되어 변이 $N$개인 볼록 다각형을 이룬다. 나머지 $N - 3$개의 도로는 끝점을 제외하고 서로 교차하지 않도록 지점들을 잇는다.

도로를 따라 걷던 맬나르 씨는 어떤 지점도 두 번 거치지 않고 출발점으로 돌아왔다. 그는 이것이 흔한 일이라고 여기고, 도시의 혼란도를 단순 닫힌 루프의 개수로 정의했다.

단순 닫힌 경로는 지점의 수열 $V_1, V_2, \dots , V_m$으로, 모든 $i = 1, 2, \dots , m - 1$에 대해 $V_i$와 $V_{i+1}$이 도로로 연결되고, $V_m$과 $V_1$도 도로로 연결되어 있다. 한 경로를 순환 이동하거나 뒤집어서 다른 경로를 얻을 수 있으면 두 경로는 같다고 본다. 예를 들어 $(1, 2, 3, 4)$는 $(2, 3, 4, 1)$과 같다. 단순 닫힌 루프는 같은 경로끼리 묶은 집합이다.

이 도시의 혼란도를 계산해 달라.

첫 줄에 지점의 수를 나타내는 정수 $N$ ($1 \le N \le 2 \cdot 10^5$)이 주어진다.

이어지는 $N - 3$개의 줄에는 $i$번째 도로가 잇는 지점의 번호 $X_i$, $Y_i$ ($1 \le X_i, Y_i \le N$)가 각각 주어진다.

도시의 혼란도를 $10^9 + 7$로 나눈 나머지를 출력한다.