Topological Sorting of a Tree#260
You are given a tree with vertices, numbered from to . The root of the tree is the vertex with number . For each from to , let's define p_v as the number of the vertex adjacent to that lies on the simple path between vertex and the root. Each edge (p_v, v) is labeled with the symbol «<» or «>».
Find the number of ways to place the numbers from to in the vertices of the tree, such that each number is used exactly once and all the relationships indicated on the edges are satisfied. That is, for all edges with the symbol «<», a[p_v] < a[v] should hold, and for all edges with the symbol «>», a[p_v] > a[v] should hold.
Since the answer can be very large, output it modulo 10^9 + 7.
The first line contains a single integer (1 \leq n \leq 3\,000) - the number of vertices in the tree.
Each of the next n-1 lines contains a single integer p_i (1 \leq p_i < i) and a character c_i (c_i \in \{«<», «>»), indicating that the edge between vertices with indices p_i and is labeled with the symbol c_i. Note that the indexing starts from .
Output a single integer - the number of ways to arrange all numbers from to in the vertices of the tree such that all the relationships indicated on the edges are satisfied. Note that you should output the remainder of the division by 10^9 + 7, not the actual answer.
Example
Example 1
Example 2
( points) n \leq 10;
( points) n \leq 18;
( points) c_i = '<';
( points) p_i = 1;
( points) p_i = i - 1, 1 \leq n \leq 200;
( points) p_i = i - 1;
( points) n \leq 200;
( points) no additional constraints.