[AdditionalFile5240.zip](file://AdditionalFile5240.zip?type=additional_file)

#5240. 「UOI 2020 Stage 4 Day2」树的拓扑排序

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2020 Stage 4 Day2 T3. Топологічні сортування дерева

给定一棵有 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$。树的根是编号为 $1$ 的顶点。对于每个顶点 $v$（从 $2$ 到 $n$），定义 $p_v$ 为与 $v$ 相邻且位于顶点 $v$ 到根的简单路径上的顶点编号。在每条边 $(p_v, v)$ 上写有一个符号 $\texttt{<}$ 或 $\texttt{>}$。

找出将数字 $1$ 到 $n$ 写入树顶点的方法数量，使得每个数字恰好使用一次，并且满足所有边上标示的关系。即对于所有标有 $\texttt{<}$ 的边，必须满足 $a[p_v] < a[v]$，对于所有标有 $\texttt{>}$ 的边，必须满足 $a[p_v] > a[v]$。

由于答案可能非常大，请输出答案对 $10^{9} + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 3000)$，表示树的顶点数量。

接下来的 $n-1$ 行，每行包含一个整数 $p_i$ $(1 \leq p_i < i)$ 和一个字符 $c_i$ $(c_i \in \{\texttt{<}, \texttt{>}\})$，表示顶点 $p_i$ 和 $i$ 之间的边上标有符号 $c_i$。请注意，这里的 $i$ 从 $2$ 开始编号。

输出格式

输出一个整数，表示将数字 $1$ 到 $n$ 分配到树顶点上并满足所有边上关系的方法数量。请注意，需要输出的是答案对 $10^{9} + 7$ 取模后的结果，而非原始答案。

样例 1

输入

4
1 <
2 <
3 >

输出

3

样例 2

输入

4
1 <
1 <
1 <

输出

6

样例 3

输入

5
1 <
1 <
3 >
3 >

输出

18

数据范围与提示

详细子任务附加限制及分值如下表所示：