National Olympiad in Informatics, China, 2001

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.

1. SS expressions consist of only the characters {, }, [, ], (, and ).
2. An empty sequence is an SS expression.
3. If ~A~ is an SS expression, and ~A~ does not contain the characters {, }, [, or ], then (~A~) is an SS expression.
4. If ~A~ is an SS expression, and ~A~ does not contain the characters {, or }, then [~A~] is an SS expression.
5. If ~A~ is an SS expression, then {~A~} is an SS expression.
6. 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 ~L_1~, ~L_2~, ~L_3~, and ~D~. Find the number of SS expressions with depth ~D~, containing exactly ~L_1~ pairs of {}, ~L_2~ pairs of [], and ~L_3~ pairs of (). Take this number modulo the current year ~11\,380~. 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.

Input Specification

The input consists of one line, with 4 space-separated integers ~L_1~, ~L_2~, ~L_3~, and ~D~ ~(0 \le L_1, L_2, L_3 \le 10; 0 \le D \le 30)~.

Output Specification

The output should consist of a single integer - the secret number.

Sample Input

1 1 1 2

Sample Output

8

Problem translated to English by Alex.