SPOJ.com - Problem AEROLITE

AEROLITE - The Secret of an Aerolite

A huge aerolite had fallen in Antarctica!!!Many disasters happened and lots of people lost their lives, homes or even everything.Blue Mary, the well-known scientist, is to work out the secret of this aerolite for further study.

Blue Mary has found out that their are some numbers on this aerolite, 5 per line:

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

With her genius, Blue Mary knows that the 5th number is the key to solve the problem, but in some lines the 5th numbers were destoryed and we cannot know what they are instantly.

After some days, she finds out the way to calculate the 5th number finally, which is:

A Regular Expression(RE) is a string which only contains characters '{','[','(',')',']','}' and satisfies the rules below.
An empty string is an RE.
If there's no character '[',']','{','}' in RE A, then (A) is an RE.
If there's no character '{','}' in RE A, then [A] is an RE.
If A is an RE, {A} is an RE.
If both A and B are REs, AB is an RE.

For example "()(())[]", "{()[()]}", "{{[[(())]]}}"(all without quotes) are REs and "()([])()","[()" are not REs.

The deep of an RE A, D(A), is defined as below:

If A is an empty string,D(A)=0;
If A can be written as BC, D(A)=max(D(B),D(C));
If A can be written as (B) or [B] or {B}, D(A)=D(B)+1.

Such as D("(){()}[]")=2.

Suppose the first 4 numbers in current line are L1,L2,L3 and D, then the 5th number in current line is the number of REs modudo 11380.Each of the REs must have a depth of D and is made of L1 {}, L2 [] and L3 ().

Now Mary needs your help to work out the 5th number.

Input

Input contains exactly 10 test cases.Each test case contains one line, which contains 4 numbers L1,L2,L3,D(0<=L1,L2,L3<=10, 0<=D<=30), separated by single spaces.

Output

Ten lines, each contains a single integer denoted the 5th number.

Example

Input:
1 1 1 1
0 0 6 3
1 1 1 2
[and 7 test cases more]

Output:
6
57
8
[and 7 test cases more]

Submit solution!

Added by:	Fudan University Problem Setters
Date:	2007-04-01
Time limit:	5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: C99 ERL JS-RHINO
Resource:	Chinese National Olympiad in Informatics 2001,Day 2; translated by Blue Mary

hide comments



2019-06-03 20:52:50 The time limit is very open and it allows you to even code 6D recursive top-down solution. It is a very nice problem to learn parenthesis style DP. Last edit: 2019-06-03 20:53:27
2017-12-30 06:56:36 narek @techidspoj: [ () ] {} {} [ () ] { () } [] [] { () } { [] } () () { [] } { () [] } { [] () }
2017-04-02 06:39:36 Can someone explain to me why 1 1 1 2 in the example of test case is equal to 8 ?
2016-02-15 07:10:43 Can anyone say me how to approach this problem?
2012-07-29 20:10:14 Hussain Kara Fallah L1 defines the number of pairs of {} or the number of brackets {}