Problem Description

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} :::

Input Format

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)$.

Output Format

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$.

0/2
1/0
2/1

2

Hint

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.