#NOI20012C. 陨石的秘密

陨石的秘密

Description

公元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 A 是SS表达式,且 A A 中不含字符 {, }, [, ],则 (A) (A) 是SS表达式。
  4. 如果 A A 是 SS 表达式,且 A A 中不含字符 {, },则 [A] [A] 是 SS 表达式。
  5. 如果 A A 是 SS 表达式,则 {A} \{A\} 是 SS 表达式。
  6. 如果 A A B B 都是 SS 表达式,则 AB AB 也是 SS 表达式。

一个 SS 表达式 E E 的深度 D(E) D(E) 定义如下:

$$\scriptstyle{ D(E) = \begin{cases} \scriptstyle{0}, & \scriptstyle{\text{如果 } E \text{ 是空串}} \\ \scriptstyle{D(A) + 1}, & \scriptstyle{\text{如果 } E = (A) \text{ 或者 } E = [A] \text{ 或者 } E = \{A\}, \text{ 其中 } A \text{ 是 SS 表达式}} \\ \scriptstyle{\max(D(A), D(B))}, & \scriptstyle{\text{ 如果 } E = AB, \text{其中 } A, B \text{ 是 SS 表达式}} \end{cases} } $$

例如 (){()}[] 的深度为 2 2

密文中的复杂运算是这样进行的:

设密文中每行前 4 4 个数依次为 L1,L2,L3,D L_1, L_2, L_3, D ,求出所有深度为 D D ,含有 L1 L_1 {}L2 L_2 []L3 L_3 () 的 SS 串的个数,并用这个数对当前的年份 11380 11380 求余数,这个余数就是密文中每行的第 5 5 个数,我们称之为“神秘数”。

密文中某些行的第五个数已经模糊不清,而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

Format

Input

共一行,4 4 个整数 L1,L2,L3,D L_1, L_2, L_3, D 。相邻两个数之间用一个空格分隔。

Output

共一行,包含一个整数,即神秘数。

Samples

1 1 1 2
8