题目描述

公元11380年，一颗巨大的陨石坠落在南极。陨石上刻有若干行密文，每行包含5个整数，例如：

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

科学家SS发现这些密文是一种复杂运算的结果，并定义了一种SS表达式：

1. SS表达式仅由 {, }, [, ], (, ) 组成。
2. 空串是SS表达式。
3. 如果 A 是SS表达式，且 A 不含 {, }, [, ]，则 (A) 是SS表达式。
4. 如果 A 是SS表达式，且 A 不含 {, }，则 [A] 是SS表达式。
5. 如果 A 是SS表达式，则 {A} 是SS表达式。
6. 如果 A 和 B 都是SS表达式，则 AB 也是SS表达式。

示例：

• ()(())[]、{()[()]}、{{[[(())]]}} 是合法的SS表达式。
• ()([])()、[() 不是合法的SS表达式。

深度定义：

• 空串的深度 $D(E) = 0$。
• 如果 $E = (A)$、$E = [A]$ 或 $E = \{A\}$，则 $D(E) = D(A) + 1$。
• 如果 $E = AB$，则 $D(E) = \max(D(A), D(B))$。

运算规则： 给定 $L_1$（{} 对数）、$L_2$（[] 对数）、$L_3$（() 对数）和 $D$（深度），计算所有满足条件的SS表达式的个数，并对11380取模，得到“神秘数”。

输入格式

一行，4个整数 $L_1$, $L_2$, $L_3$, $D$（$0 \leq L_1, L_2, L_3 \leq 10$，$0 \leq D \leq 30$）。

输出格式

一行，一个整数，表示神秘数（即符合条件的SS表达式个数模11380）。

示例输入

1 1 1 2

示例输出

8

题目来源

NOI 2001