该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

公元$\red {11380}$年，一颗巨大的陨石坠落在南极。

于是，灾难降临了，地球上出现了一系列反常的现象。

当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。

经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含$\red {5}$个整数：

$\red {1 ~1 ~1 ~1 ~6}$

$\red {0 ~0 ~6 ~3 ~57}$

$\red {8 ~ 0 ~11 ~3 ~2845}$

著名的科学家SS发现，这些密文实际上是一种复杂运算的结果。

为了便于大家理解这种运算，他定义了一种$\red {SS}$表达式：

1． $\red {SS}$表达式是仅由$\red {’\{‘，’\}’，’[‘，’]’，’（’，’）’}$组成的字符串。

2． 一个空串是$\red {SS}$表达式。

3． 如果$\red {A}$是$\red {SS}$表达式，且$\red {A}$中不含字符$\red {’\{‘，’\}’，’[‘，’]’}$，则$\red {(A)}$是$\red {SS}$表达式。

4． 如果$\red {A}$是$\red {SS}$表达式，且$\red {A}$中不含字符$\red {’\{‘，’\}’}$，则$\red {[A]}$是$\red {SS}$表达式。

5． 如果$\red {A}$是$\red {SS}$表达式，则$\red {\{A\}}$是$\red {SS}$表达式。

6． 如果$\red {A}$和$\red {B}$都是$\red {SS}$表达式，则$\red {AB}$也是$\red {SS}$表达式。

例如

()(())[] 
{()[()]} 
{{[[(())]]}}

都是$\red {SS}$表达式。

而

()([])() 
[()

不是$\red {SS}$表达式。

一个$\red {SS}$表达式$\red {E}$的深度$\red {D(E)}$定义如下：

例如$\red {()\{()\}[]}$的深度为$\red {2}$。

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

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

密文中某些行的第五个数已经模糊不清，而这些数字正是揭开陨石秘密的钥匙。

现在科学家们聘请你来计算这个神秘数。

输入格式

共一行，$\red {4}$个整数 $\red {L_1 ，L_2 ，L_3 ，D}$。

输出格式

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

样例

输入样例

1 1 1 2

输出样例

8

提示

$\red {0≤L _1 ,L_2 ,L_3 ≤10}$,

$\red {0≤D≤30}$