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 wellknown 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]
hide comments
sky_scraper:
20190603 20:52:50
The time limit is very open and it allows you to even code 6D recursive topdown solution. It is a very nice problem to learn parenthesis style DP. Last edit: 20190603 20:53:27 

narek:
20171230 06:56:36
@techidspoj:


techidspoj:
20170402 06:39:36
Can someone explain to me why 1 1 1 2 in the example of test case is equal to 8 ? 

raga39:
20160215 07:10:43
Can anyone say me how to approach this problem? 

Hussain Kara Fallah:
20120729 20:10:14
L1 defines the number of pairs of {} or the number of brackets {} 
Added by:  Fudan University Problem Setters 
Date:  20070401 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  Chinese National Olympiad in Informatics 2001,Day 2; translated by Blue Mary 