P17082 [COTS 2026] 寻踪 / Orijentacije（暂无数据）

2s 512M。

> **三角剖分图**：考虑 $N$ 个平面上的点，编号 $1\sim N$。$N$ 条边将这 $N$ 个点按编号顺序连成一个环，组成一个凸多边形。除此之外，还有 $(N-3)$ 条额外的非环边，保证非环边只在端点处相交。不难发现这张图恰有 $(2N-3)$ 条边。 > > 这张图的 **Hamilton 路**定义为 $1\sim N$ 的排列 $p_1\sim p_N$，满足 $\forall 1\le i\le N-1$，都有 $(p_i,p_{i+1})$ 是图中的边。 给定一张 $N$ 个点的三角剖分图。求出这张图的 Hamilton 路的数量。 定义两条 Hamilton 路 $p,q$ 不同，当且仅当存在 $1\le i\le N$ 使得 $p_i\neq q_i$。 你只需要求出答案对 $(10^9+7)$ 取模的结果。

第一行，正整数 $N$（$3\le N\le 2\cdot 10^5$）。 接下来 $(N-3)$ 行，第 $i$ 行两个正整数 $u_i,v_i$（$1 \le u_i, v_i \le N$），描述一条额外边。

输出答案对 $(10^9 + 7)$ 取模后的结果。

### 样例解释 **第一个样例解释：** 第一个样例中的图，形如一个四边形加一条对角线 $(1,3)$。  Hamilton 路有：$(1, 2, 3, 4), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 4, 1, 2), (4, 1, 2, 3), (4, 1, 3, 2), (4, 3, 1, 2)$ 和 $(4, 3, 2, 1)$。 ### 子任务 | 子任务 | 分数 | 限制条件 | | :---: | :---: | :--- | | $1$ | $5 $ | $N \le 6$ | | $2$ | $12$ | $N \le 18$ | | $3$ | $7 $ | 存在一个点，它与其他所有地点都有连边。 | | $4$ | $19$ | 每个点最多是四条边的端点。 | | $5$ | $25$ | $N \le 2000$ | | $6$ | $32$ | 无额外限制。 |