PEG Judge - NOI '01 - Secret of the Meteorite

National Olympiad in Informatics, China, 2001

Day 2, Problem 3 - Secret of the Meteorite

In the year 11380 CE, an enormous meteorite crashes into the south pole. Then, disaster breaks out. A series of abnormal phenomena begins to take place on earth. Just when earthlings are in the midst of panicking, an Antarctic expedition team made up of Chinese scientists rushed to the site of the incident. After researching, the scientists have discovered that the meteorite contains several lines of a mysterious text. Each line contains 5 integers, for example:

1 1 1 1 6
0 0 6 3 57
8 0 11 3 2845

The famous scientist SS has discovered that the text is actually the result of a complex computation. To make it easier for everyone to understand the computation, he defines a new type of SS expressions.

SS expressions consist of only the characters '{', '}', '[', ']', '(', and ')'.
An empty sequence is an SS expression.
If A is an SS expression, and A does not contain the characters '{', '}', '[', or ']', then (A) is an SS expression.
If A is an SS expression, and A does not contain the characters '{', or '}', then [A] is an SS expression.
If A is an SS expression, then {A} is an SS expression.
If A and B are both SS expressions, then AB is also an SS expression.

For example:

()(())[]
{()[()]}
{{[[(())]]}}

are all SS expressions, but:

()([])()
[()

are not SS expressions.

The depth D(E) of an SS expression E is equal to:

0, if E is an empty sequence.
D(A) + 1, if E is {A} or [A] or (A), where A is an SS expression.
max(D(A), D(B)), if E is AB, and A and B are both SS expressions.

For instance, (){()}[] has a depth of 2.

The complex computation in the secret text is performed as follows:

Let the first four integers of each line in the text be L1, L2, L3, and D. Find the number of SS expressions with depth D, containing exactly L1 pairs of {}, L2 pairs of [], and L3 pairs of (). Take this number modulo the current year 11380. The remainder is the fifth number of each line, which we will call the "secret number".

For many lines of this secret text, the secret number has been blurred out. These numbers are in fact the key to revealing the secret behind the meteorite. Now, the scientists are inviting you to help them determine the secret number.