P11391 [COCI 2024/2025 #1] 疑惑 / Zbunjenost

译自 [COCI 2024/2025 #1](https://hsin.hr/coci/) T5。$\texttt{5s,0.5G}$。满分为 $120$。

给定一个 $n$ 个顶点的凸包和它的三角剖分。 可以认为点按照顺时针顺序标号 $1\sim n$，也就是说，$\forall 1\le i\le n$，点 $i$ 和点 $(i\bmod n+1)$ 间有边相连。 定义一条长度为 $m$（$m\ge 3$）的**简单回路** $a_0,a_1,\cdots,a_{m-1}$ 为满足以下条件的序列： - $\forall i\in [0,m)$，$1\le a_i\le n$； - $\forall 0\le i\lt j\lt m$，$a_i\neq a_j$； - $\forall i\in [0,m)$，顶点 $a_i,a_{(i+1)\bmod m}$ 间有边相连。 定义两条回路**本质相同**，当且仅当一条回路可以通过翻转（reverse）或者循环移位或者翻转+循环移位得到另一条回路。 求出凸包内本质不同的回路条数，对 $(10^9+7)$ 取模。

第一行，一个正整数 $n$。 接下来 $(n-3)$ 行，每行两个正整数 $x,y$，描述三角剖分的一条边。

输出一行一个整数，表示答案对 $(10^9+7)$ 取模后的结果。

#### 样例解释 - 样例 $1$ 解释：$[1,2,3]$，$[1,4,3]$，$[1,2,3,4]$ 是合法的回路。 - 样例 $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 n\le 2\times 10^5$； - 给定的是合法三角剖分。 | 子任务编号 | $n\le$ | 特殊性质 | 得分 | | :--: | :--: | :--: |:--: | | $ 1 $ | $15$ | | $ 13 $ | | $ 2 $ | $300$ | | $ 18 $ | | $ 3 $ | $2\times 10^3$ | | $ 34 $ | | $ 4 $ | $2\times 10^5$ | A | $ 15 $ | | $ 5 $ | $2\times 10^5$ | | $ 40 $ | - 特殊性质 A：$\forall 3\le i\le n-1$，点 $1$ 与点 $i$ 间有边相连。