U509549 [COCI2024/2025 #1] Zbunjenost

Malnar 决定通过随机飞行来度过他的暑假，环游世界。过了一段时间，他发现自己身处一个未知国家的首都，那里的街道让他想起了三角测量！更准确地说，这座城市由 $N$ 个有趣的地点组成，编号从 $1$ 到 $N$，由 $2N-3$ 条街道连接。位置 $1,2,\dots,N$ 依次连接成一个有 $N$ 条边的凸多边形。剩余的 $N-3$ 条街道以没有两条街道交叉的方式连接各个地点，除非它们的尽头会有交叉。 在漫步在这个国家首都的街道上时，Malnar 发现自己回到了起点，没有访问过任何位置超过一次。他有点困惑地意识到这完全正常，并提出了一个简单的封闭环的数量作为困惑的量度。简单的封闭行走是位置 $V_1,V_2,\dots,V_m$ 的序列，其中 $V_i$ 通过街道与位置 $V_{i+1}$ 相连，对于每个 $i=1,2,\dots,m-1$，且位置 $V_m$ 与 $V_1$ 相连。如果两个行走可以通过另一个的循环旋转或通过另一个的反转获得，则它们是等效的。例如，步行 $(1,2,3,4)$ 等于步行 $(2,3,4,1)$。简单闭环是等效步行的集合。Malnar 现在请求你帮助计算这个城市的困惑程度!

第一行输入正整数 $N$，位置的数目。 在接下来的 $N-3$ 行中输入整数 $X_i$ 和 $Y_i$，这些位置由第 $i$ 条街道连接。

求出这个城市的迷惑值，并对他 $\bmod 10^9+7$

【样例解释 #1】 如图，每个圈都用不同的颜色来着色。  【样例解释 #2】 每个圈依次是 $(1, 2, 3), (1, 3, 5), (3, 4, 5), (1, 2, 3, 5), (1, 3, 4, 5), (1, 2, 3, 4, 5)$。 【样例解释 #3】 每个圈依次是 $(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)$。 【数据范围】 对于 $100\%$ 的数据，保证 $1\le X_i,Y_i\le N\le 2\times10^5$。 | Substask | 分数 | 约束条件 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 样例 | | $1$ | $13$ | $N\le15$ | | $2$ | $18$ | $N\le300$ | | $3$ | $34$ | $N\le2000$ | | $4$ | $15$ | 对于所有 $k=3,4,\dots,N-1$，位置 $1$和 $k$ 是相连的。 | | $5$ | $40$ | 无 |