P17082 [COTS 2026] Tracking / Orijentacije（No testdata yet）

2 s, 512 MB.

**Triangulation graph**: Consider $N$ points on the plane, numbered $1 \sim N$. The $N$ boundary edges connect these $N$ points in the order of their indices to form a cycle, making a convex polygon. In addition, there are $(N-3)$ extra non-boundary edges, and they are guaranteed to intersect only at their endpoints. It is easy to see that this graph has exactly $(2N-3)$ edges. A **Hamiltonian path** in this graph is defined as a permutation $p_1 \sim p_N$ of $1 \sim N$ such that for all $1 \le i \le N-1$, $(p_i, p_{i+1})$ is an edge in the graph. Given a triangulation graph with $N$ vertices, find the number of Hamiltonian paths in this graph. Two Hamiltonian paths $p, q$ are considered different if and only if there exists some $1 \le i \le N$ such that $p_i \ne q_i$. You only need to output the answer modulo $(10^9+7)$.

The first line contains a positive integer $N$ ($3 \le N \le 2 \cdot 10^5$). The next $(N-3)$ lines each contain two positive integers $u_i, v_i$ ($1 \le u_i, v_i \le N$), describing an extra edge.

Output the answer modulo $(10^9 + 7)$.

### Sample Explanation **Explanation of the first sample:** The graph in the first sample is a quadrilateral with one diagonal $(1,3)$.  The Hamiltonian paths are: $(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)$ and $(4, 3, 2, 1)$. ### Subtasks | Subtask | Score | Constraints | | :---: | :---: | :--- | | $1$ | $5$ | $N \le 6$ | | $2$ | $12$ | $N \le 18$ | | $3$ | $7$ | There exists a vertex that is connected by an edge to every other vertex. | | $4$ | $19$ | Each vertex is the endpoint of at most four edges. | | $5$ | $25$ | $N \le 2000$ | | $6$ | $32$ | No additional constraints. | Translated by ChatGPT 5