Malnar 先生决定通过随机飞行来环游世界。过了一段时间，他发现自己身处一个未知国家的首都，那里的街道让他想起了三角剖分！更准确地说，这座城市由 $N$ 个有趣的地点组成，编号从 $1$ 到 $N$，它们之间由 $2N-3$ 条街道连接。地点 $1, 2, \dots, N$ 按顺序连接，形成一个 $N$ 边形的凸多边形。其余的 $N-3$ 条街道连接这些地点，使得除了端点外，没有任何两条街道相交。
在漫步这座城市的街道时，Malnar 先生发现自己回到了出发的地点，且没有访问过任何地点超过一次。他感到有些困惑，于是意识到这其实是很正常的，并提出了一个“困惑度”的度量，即简单闭合回路的数量。简单闭合路径是一个地点序列 $V_1, V_2, \dots, V_m$，使得对于每个 $i=1, 2, \dots, m-1$，地点 $V_i$ 都通过街道与地点 $V_{i+1}$ 相连，且地点 $V_m$ 与 $V_1$ 相连。如果两条路径可以通过循环移位或反转得到，则称它们是等价的。例如，路径 $(1, 2, 3, 4)$ 与路径 $(2, 3, 4, 1)$ 等价。简单闭合回路是一组等价的路径。现在，Malnar 先生请求你帮助计算这座城市的困惑度！
输入格式
第一行包含一个整数 $N$ ($1 \le N \le 2 \cdot 10^5$)，表示有趣地点的数量。
接下来的 $N-3$ 行，每行包含两个整数 $X_i, Y_i$ ($1 \le X_i, Y_i \le N$)，表示第 $i$ 条街道连接的地点编号。
输出格式
在唯一的一行中输出该城市的困惑度，结果对 $10^9 + 7$ 取模。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 13 | $N \le 15$ |
| 2 | 18 | $N \le 300$ |
| 3 | 34 | $N \le 2000$ |
| 4 | 15 | 地点 $1$ 与所有 $k=3, 4, \dots, N-1$ 相连 |
| 5 | 40 | 无附加限制 |
样例
输入格式 1
4 1 3
输出格式 1
3
说明
第一个样例的说明： 在草图中，每个回路都用不同的颜色标出。
输入格式 2
5 1 3 3 5
输出格式 2
6
说明
第二个样例的说明： 代表回路的路径有：$(1, 2, 3), (1, 3, 5), (3, 4, 5), (1, 2, 3, 5), (1, 3, 4, 5), (1, 2, 3, 4, 5)$。
输入格式 3
6 2 4 4 6 6 2
输出格式 3
11
说明
第三个样例的说明： 代表回路的路径有：$(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)$。