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.

UESTC

2015 Multi-University Training Contest 7