P12639 [UOI 2020] Topological Sorting of a Tree

给定一棵包含 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$。树的根节点是编号为 $1$ 的顶点。对于每个 $v$（从 $2$ 到 $n$），定义 $p_v$ 为与 $v$ 相邻且在 $v$ 到根节点路径上的顶点编号。每条边 $(p_v, v)$ 上都标有符号 $\tt{}$。 求将数字 $1$ 到 $n$ 填入树的所有顶点中的方案数，要求每个数字恰好使用一次，且满足所有边上标明的约束关系。具体来说： - 对于标有 $\tt{}$ 的边，需满足 $a[p_v] > a[v]$ 由于答案可能很大，请输出对 $10^9 + 7$ 取模的结果。

第一行包含一个整数 $n$（$1 \leq n \leq 3\,000$）——树中顶点的数量。 接下来的 $n-1$ 行，每行包含一个整数 $p_i$（$1 \leq p_i < i$）和一个字符 $c_i$（$c_i \in \{\tt{}\}$），表示顶点 $p_i$ 和 $i$ 之间的边标有符号 $c_i$。注意顶点编号从 $2$ 开始。

输出一个整数——将数字 $1$ 到 $n$ 填入顶点且满足所有边约束的方案数。注意需要输出对 $10^9 + 7$ 取模后的结果。

- （$8$ 分）$n \leq 10$； - （$6$ 分）$n \leq 18$； - （$10$ 分）所有 $c_i = \tt{