Description

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

求将数字 $1$ 到 $n$ 填入树的所有顶点中的方案数，要求每个数字恰好使用一次，且满足所有边上标明的约束关系。具体来说：

• 对于标有 $\tt{<}$ 的边，需满足 $a[p_v] < a[v]$
• 对于标有 $\tt{>}$ 的边，需满足 $a[p_v] > a[v]$

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

Input Format

第一行包含一个整数 $n$（$1 \leq n \leq 3\,000$）——树中顶点的数量。

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

Output Format

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

4
1 <
2 <
3 >

3

4
1 <
1 <
1 <

6

5
1 <
1 <
3 >
3 >

18

Hint

• （$8$ 分）$n \leq 10$；
• （$6$ 分）$n \leq 18$；
• （$10$ 分）所有 $c_i = \tt{<}$；
• （$4$ 分）所有 $p_i = 1$；
• （$13$ 分）$p_i = i - 1$，且 $1 \leq n \leq 200$；
• （$19$ 分）所有 $p_i = i - 1$；
• （$24$ 分）$n \leq 200$；
• （$16$ 分）无额外限制。

翻译由 DeepSeek V3 完成