In the year 11380 AD, a massive meteorite crashed into Antarctica. Consequently, a disaster struck, and a series of anomalous phenomena appeared on Earth. As people were filled with anxiety, a team of Chinese scientists arrived at the scene.

After some investigation, the scientists discovered several lines of ciphertext engraved on the meteorite. Each line contains 5 integers:

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

The famous scientist SS discovered that these ciphertexts are actually the result of a complex calculation. To help everyone understand this calculation, he defined an SS expression:

1. An SS expression is a string consisting only of '{', '}', '[', ']', '(', ')'.
2. An empty string is an SS expression.
3. If $A$ is an SS expression and $A$ does not contain the characters '{', '}', '[', ']', then $(A)$ is an SS expression.
4. If $A$ is an SS expression and $A$ does not contain the characters '{', '}', 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. However: ()([])() [() are not SS expressions.

The depth $D(E)$ of an SS expression $E$ is defined as follows:

$$ D(E) = \begin{cases} 0, & \text{if } E \text{ is an empty string} \\ D(A) + 1, & \text{if } E = (A) \text{ or } E = [A] \text{ or } E = \{A\}, \text{ where } A \text{ is an SS expression} \\ \max(D(A), D(B)), & \text{if } E = AB, \text{ where } A, B \text{ are SS expressions} \end{cases} $$

For example, the depth of (){()}[] is 2.

The complex calculation in the ciphertext is performed as follows: Given the first 4 numbers in each line of the ciphertext as $L_1, L_2, L_3, D$, find the number of SS expressions with depth $D$ that contain $L_1$ pairs of '{}', $L_2$ pairs of '[]', and $L_3$ pairs of '()'. Calculate the remainder of this count when divided by the current year 11380. This remainder is the 5th number in each line of the ciphertext, which we call the "mysterious number."

Some of the 5th numbers in the ciphertext are already blurred, and these numbers are the keys to unlocking the secrets of the meteorite. Now, the scientists have hired you to calculate this mysterious number.

Input

A single line containing 4 integers $L_1, L_2, L_3, D$. The numbers are separated by a space. ($0 \le L_1 \le 10, 0 \le L_2 \le 10, 0 \le L_3 \le 10, 0 \le D \le 30$)

Output

A single line containing one integer, the mysterious number.

Examples

Input 1

1 1 1 2

Output 1

8