题目描述

本题只考虑顶点编号为 $0,1,\ldots,n-1$ 的连通、无向、简单图，即图中不存在自环和重边。

对图执行如下深度优先搜索。访问一个顶点时，总是按照顶点编号从小到大的顺序枚举它的邻点。

DFS(d, v):
    输出 d/v
    将顶点 v 标记为已访问
    W = v 的所有邻点，按编号从小到大排列
    对 W 中的每个 w：
        若 w 尚未访问：
            DFS(d + 1, w)

现在给定某个未知图执行 DFS(0, n - 1) 时输出的完整文本。

请计算有多少个不同的连通无向简单图会产生与输入完全相同的 DFS 输出。

例如，下面的输出：

0/2
1/0
2/1

可以由下图中的两个不同图产生：

输入格式

输入就是某个未知连通无向简单图执行 DFS(0, n - 1) 后得到的文本。

输入共有 $n$ 行，每行格式为：

d/v

其中：

• $d$ 是顶点 $v$ 在 DFS 树中的深度；
• 第一行一定是 0/n-1；
• 输入中没有单独给出 $n$，应以读到文件结尾为止的行数作为 $n$。

保证输入确实能够由至少一个符合条件的图产生。

输出格式

输出满足条件的图的数量，对

取模。

数据范围

• $1\le n\le 2\cdot 10^5$。

子任务

样例

输入

0/2
1/0
2/1

输出

2