题目描述

给定一棵包含 $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$ 取模的结果。

输入格式

第一行包含一个整数 $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$ 开始。

输出格式

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

输入输出样例 #1

输入 #1

4
1 <
2 <
3 >

输出 #1

3

输入输出样例 #2

输入 #2

4
1 <
1 <
1 <

输出 #2

6

输入输出样例 #3

输入 #3

5
1 <
1 <
3 >
3 >

输出 #3

18

说明/提示

• （$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$ 分）无额外限制。