题目描述

你可能已经熟悉著名的 DFS（深度优先搜索）图遍历算法。本题只考虑连通无向简单图（不含自环和重边），其顶点编号为 $0,1,\ldots,n-1$。DFS 算法按如下方式输出深度和顶点：

DFS(d, v):
    output d/v
    mark vertex v as visited
    W = the list of neighbors of v ordered by increasing numbers
    for each w in W:
        if vertex w has not yet been visited:
            DFS(d + 1, w)

编写一个程序，输出满足如下条件的不同图的数量：调用 DFS(0,n-1) 时，其输出与输入给定的输出完全相同。例如，输出

0/2
1/0 
2/1 

可以由以下两个连通无向简单 $3$ 顶点图中的任意一个调用 DFS(0,2) 得到：

:::align{center} :::

输入格式

输入内容是对某个未知的 $n$ 顶点连通无向简单图调用 DFS(0,n-1) 所得到的输出。因此，输入共包含 $n$ 行，每行格式为 d/v，第一行为 0/(n-1)。

输出格式

输出满足要求的不同图的数量。由于答案可能非常大，请输出其对 $1\,000\,000\,007$ 取模后的结果。

0/2
1/0
2/1

2

提示

【限制条件】

• $1\le n\le 2\times 10^5$

【子任务】

• 子任务 $1$（$10$ 分）：$n\le 6$。
• 子任务 $2$（$20$ 分）：$n\le 500$。
• 子任务 $3$（$20$ 分）：$n\le 10^4$。
• 子任务 $4$（$10$ 分）：对于每个 $i\in\{2,\ldots,n\}$，输入的第 $i$ 行均为 $(i-1)/(i-2)$。
• 子任务 $5$（$20$ 分）：对于每个 $i\in\{2,\ldots,n\}$，输入的第 $i$ 行均为 $(i-1)/v$，其中某个 $v\in\{0,\ldots,n-2\}$。
• 子任务 $6$（$20$ 分）：无额外限制。

翻译由 ChatGPT-5.6 完成