레이팅 미적용Mr. Malnar decided to spend his summer traveling around the world by flying
randomly. After some time, he found himself in an unknown country’s capital
where streets reminded him of a triangulation! More precisely, the city consists
of \(N\) interesting locations numbered from 1 to \(N\) connected by 2N - 3 streets.
Locations 1, 2, . . ., \(N\) are connected in that order to form a convex polygon with
\(N\) sides. Remaining \(N - 3\) streets connect locations in such a way that no two
streets cross, except maybe at their ends.
While walking the streets of this country’s capital Mr. Malnar found himself at the location where he
started from without visiting any location more than once. A bit confused he came to the realization
that this is completely normal and came up with a measure of confusion as the number of simple closed
loops. Simple closed walk is a sequence of locations \(V_{1}\), \(V_{2}\), . . ., \(V_{m}\) such that \(V_{i}\) is connected via street
with location \(V_{\)i+1\(}\) for every \(i = 1\), 2, . . . , \(m - 1\) and that location \(V_{m}\) is connected with \(V_{1}\). Two walks are
equivalent if one can be obtained by a cyclic rotation of the other, or by reversing the other. For example,
walk (1, 2, 3, 4) is equivalent to the walk (2, 3, 4, 1). Simple closed loop is a set of equivalent walks. Mr.
Malnar now asks for your help in calculating the confusion of this city!
In the first line is an integer \(N\) (\(1 \le N \le 2 \cdot 10^{5}\)), number of interesting locations.
In the next \(N - 3\) lines are integers \(X_{i}\), \(Y_{i}\) (\(1 \le X_{i}\), \(Y_{i} \le N\)), labels of locations connected by \(i\)-th street.
In the first and only line output the confusion of the given city modulo \(10^{9} + 7\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 13점 | \(N \le 15\) |
2 | 18점 | \(N \le 300\) |
3 | 34점 | \(N \le 2000\) |
4 | 15점 | Locations 1 and \(k\) are connected for all \(k = 3\), 4, . . . , \(N - 1\). |
5 | 40점 | No additional constraints. |
4
1 335
1 3
3 566
2 4
4 6
6 211Clarification of the first example:
On the sketch, each loop is colored in a different color.
Clarification of the second example:
Walks that represent loops are: (1, 2, 3), (1, 3, 5), (3, 4, 5), (1, 2, 3, 5), (1, 3, 4, 5), (1, 2, 3, 4, 5).
Clarification of the third example:
Walks that represent loops are: (1, 2, 6), (2, 3, 4), (4, 5, 6), (2, 4, 6), (1, 2, 4, 6), (2, 3, 4, 6), (2, 4, 5, 6),
(1, 2, 3, 4, 6), (2, 3, 4, 5, 6), (1, 2, 4, 5, 6), (1, 2, 3, 4, 5, 6).