我必须翻译一下这神人写的题意。

凸包：凸多边形

三角剖分：把这个凸多边形用互不交叉的对角线，分成一个个三角形。 （这里指顶点可以重合，但边不能交叉）

题目要求的：给你凸多边形和它的三角剖分，问有多少条严格不相同的回路？

不想写了看代码注释，wyh 的方法太过于逆天，写不了文字证明。

时间复杂度：dfs 时候每个顶点被调用的次数等于其入度，而总入度 = 总边数 = $O(N)$。

所以瓶颈居然在排序 $O(NlogN)$。

这集神了。

// 代码 & 做法 by wyh
// 注释 by proMatheus，包含个人理解

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL P = 1e9 + 7;
const int N = 2e5 + 10;

LL ans;                     // 最终答案（本质不同的回路总数）
vector<int> G[N];      // 邻接表只存储从编号小指向编号大的边

// 实际上就是取不重复的三元组 (x, y, z)，连成一个“三角形”
// 有几个三角形就是有几个回路
// 为了三元组的严格不同，我们强制要求 x < y < z
// 同时保证 x 是有边直接指向 y 的，z 则是该回路中编号最大的点
// 因此我们将点按编号小指向编号大连边
// 可以保证所有可能的回路都能唯一构成一个这样的三元组

// 还有一个点，题目保证对角线不相交
// 这样也是方便求回路时遍历的点一定是从小到大

LL dfs(int x) {
    LL w = 0;
    for (int y : G[x]) if (y != G[x].back()) {
        // 这里 x 作为第一个点，y 及 y 前面与 x 相连的点作为第二个点（的人选）
        // 让 y 去寻找有多少个第三个点符合的人选
        // 那就有可爱的小朋友要问了：
        // 为什么不遍历 x 连的最大的点呢？
        // 还有为什么找不到点也会返回 1 呢？
        // 你可以当作这些找不到的点返回 1，就是和那个最大的点配对
        // 而且，x 能连到最大的点，如果它作为第二个点
        // 我们无法找到比它大的点，还能走回 x
        // 因为走边是严格按照从小到大走的
        w ++;                               
        w = (w * dfs(y)) % P; 
        ans = (ans + w) % P;       
    }
    return (w + 1) % P; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i < n; i ++) {
        G[i].push_back(i + 1);
    }
    
    G[1].push_back(n);
    // 1 和 n 之间也是严格从小到大
    // 同时，n 作为 1 能连到最大的点
    // 它更没有招数再找一个更大的点作为第三个点

    for (int i = 1; i <= n - 3; i ++) {
        int x, y;
        cin >> x >> y;
        if (x > y) {
            swap(x, y);
        }
        G[x].push_back(y);
    }

    for (int i = 1; i <= n; i++) {
        sort(G[i].begin(), G[i].end());
        // 必须给每个连到的点排序
        // 我们必须保证在当前点的下一层按顺序遍历
        // 这样才好统计三元组
    }

    LL t = dfs(1);

    cout << ans << "\n";
    return 0;
}