odd doctor 已更新

Tree Maker

Time Limit
Memory Limit
Judge Program

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.

Sample Input:
3 3
4 3
3 3
Sample Output:
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.


2015 Multi-University Training Contest 7