| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 48 | 29 | 22 | 55.000% |
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 2ドルN - 3$ streets. Locations 1,ドル 2, \dots , 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, \dots , V_m$ such that $V_i$ is connected via street with location $V_{i+1}$ for every $i = 1, 2, \dots , 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ドル ≤ N ≤ 2 \cdot 10^5$), number of interesting locations.
In the next $N - 3$ lines are integers $X_i,ドル $Y_i$ (1ドル ≤ X_i , Y_i ≤ 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 ≤ 15$ |
| 2 | 18 | $N ≤ 300$ |
| 3 | 34 | $N ≤ 2000$ |
| 4 | 15 | Locations 1ドル$ and $k$ are connected for all $k = 3, 4, \dots , N - 1$. |
| 5 | 40 | No additional constraints. |
4 1 3
3
On the sketch, each loop is colored in a different color.
5 1 3 3 5
6
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)$.
6 2 4 4 6 6 2
11
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)$.