P17164 [CEOI 2026] DFS

You might already be familiar with the famous DFS (depth-first search) algorithm for traversing a graph. In this problem, we will only consider connected undirected simple graphs (without loops and parallel edges) with vertices numbered $0,1,\ldots,n-1$, and the DFS algorithm will output depths and vertices as follows: ``` 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) ``` Write a program that outputs the number of different graphs for which the call DFS($0$, $n-1$) produces the same printout as the one given on the input. For example, the output $0/2$ $1/0$ $2/1$ is produced by calling DFS($0$, $2$) on either of the following two connected undirected simple $3$-vertex graphs: :::align{center}  :::

The input is the output of the call DFS($0$, $n-1$) on an unknown $n$-vertex connected undirected simple graph. The input thus consists of $n$ lines in the format $d/v$, with the first line being $0/(n-1)$.

Print the number of different graphs with the required property. Because this number can be very large, output the result modulo $1\,000\,000\,007$.

### Constraints - $1\le n\le 2\cdot 10^5$ ### Subtasks - Subtask $1$ ($10$ points): $n\le 6$. - Subtask $2$ ($20$ points): $n\le 500$. - Subtask $3$ ($20$ points): $n\le 10^4$. - Subtask $4$ ($10$ points): For each $i\in\{2,\ldots,n\}$, the $i$-th input line is $(i-1)/(i-2)$. - Subtask $5$ ($20$ points): For each $i\in\{2,\ldots,n\}$, the $i$-th input line is $(i-1)/v$ for some $v\in\{0,\ldots,n-2\}$. - Subtask $6$ ($20$ points): No additional constraints.