Problem Description

In the year 11380 AD, a huge meteorite fell in Antarctica. Then disaster struck, and a series of abnormal phenomena appeared on Earth. When people were extremely anxious, a Chinese scientific expedition to Antarctica arrived at the scene. After some investigation, the scientists found several lines of ciphertext carved on the meteorite, and 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 results of a complex operation. To make this operation easier to understand, he defined an SS expression:

1. An SS expression is a string consisting only of {, }, [, ], (, ).
2. The 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.

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

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

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

The complex operation in the ciphertext is performed as follows:

Let the first $4$ numbers in each line of the ciphertext be $L_1, L_2, L_3, D$ in order. Compute the number of all SS strings with depth $D$, containing $L_1$ pairs of {}, $L_2$ pairs of [], and $L_3$ pairs of (); then take this number modulo the current year $11380$. This remainder is the $5$-th number in that line of the ciphertext, and we call it the “mysterious number”.

The fifth number in some lines of the ciphertext has become blurry, and these numbers are the key to uncovering the meteorite’s secret. Now the scientists hire you to compute this mysterious number.

Input Format

One line with $4$ integers $L_1, L_2, L_3, D$. Adjacent numbers are separated by a single space.

Output Format

One line containing one integer, the mysterious number.

1 1 1 2

8

Hint

$0 \le L_1, L_2, L_3 \le 10$，$0 \le D \le 30$。

Translated by ChatGPT 5