Tree Maker
Tree Lover loves trees crazily.
One day he invents an interesting game which is named Tree Maker.
In this game, all trees are binary trees.
Initially, there is a tree with only one vertex and a cursor on it. Tree Lover can control the cursor to apply 5 operations to build a tree, and their formats are following:
0 : Jump to the parent of the current vertex.
1 : Jump to the left child of the current vertex.
2 : Jump to the right child of the current vertex.
3 x : Generate a tree with x vertices arbitrarily and make it the left subtree of the current vertex.
4 x : Generate a tree with x vertices arbitrarily and make it the right subtree of the current vertex.
When applying an operation, the log system will log down a record of it.
Tree Lover played this game for a whole day yesterday. As a forgetful man, although Tree Lover knew the shape of the tree while playing, after a sleep he forgot it.
All he has now is the logs of operations.
Tree Lover wants to know: how many possible shapes of the tree can have yesterday according to the logs?
Can you answer this question?
The input consists of multiple test cases.
For each test case:
The first line is an integer n (1 <= n <= 500), denoting the lines of logs.
Then follow n lines of logs. The formats of logs are as described above.
The integer x of operation 3 and 4 is positive.
In each case, the number of vertices of the tree will never exceed 500.
You can assume that the cursor will never jump to a non-existent vertex.
If the left child of a vertex exists, operation 3 will not be applied on this vertex, and operation 4 is similar.
For each test case, ouput a single line “Case #x: y”, where x is the case number, starting from 1, and y is the answer to Tree Lover’s question.
Because the answer can be large, please output the answer mod 1000000007.
2 3 3 4 3 2 3 3 1
Case #1: 25 Case #2: 5
Because the tree is a binary tree, if left and right subtrees of a vertex are of different shapes, after swapping them, the new tree is considered different from the original one.
Submit