题目背景

译自 COCI 2024/2025 #1 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)$ 取模后的结果。

4 
1 3

3

5
1 3
3 5

6

6
2 4
4 6
6 2

11

提示

样例解释

• 样例 $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$；
• 给定的是合法三角剖分。

• 特殊性质 A：$\forall 3\le i\le n-1$，点 $1$ 与点 $i$ 间有边相连。