Topological Sorting of a Tree
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 as the number of the vertex adjacent to that lies on the simple path between vertex and the root. Each edge 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 «<
», should hold, and for all edges with the symbol «>
», should hold.
Since the answer can be very large, output it modulo .
Input
The first line contains a single integer () - the number of vertices in the tree.
Each of the next lines contains a single integer () and a character («<
», «>
»), indicating that the edge between vertices with indices and is labeled with the symbol . Note that the indexing starts from .
Output
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 , not the actual answer.
Examples
Scoring
( points) ;
( points) ;
( points) '
<
';( points) ;
( points) ;
( points) ;
( points) ;
( points) no additional constraints.