Byteotian 公司 0101010 生产儿童玩具。0101010 公司非常出名，他们的玩具被认为是顶级的。令员工们感到惊恐的是，他们最近生产的四款泰迪熊模型：$A_1$、$A_2$、$B_1$ 和 $B_2$ 存在一个潜在缺陷：如果我们取出三个模型名称中字母相同，或者数字相同的泰迪熊并将它们排成一排，这些泰迪熊就会受到不可修复的损坏。

如果一排泰迪熊中没有任何三个连续的泰迪熊的模型名称字母相同，也没有任何三个连续的泰迪熊的模型名称数字相同，我们就称这排泰迪熊是安全排列的。

Byteasar 拥有一堆泰迪熊，其中只有这四种模型——毕竟他才刚刚长大到可以玩泰迪熊的年纪。更糟糕的是，Byteasar 喜欢把他的泰迪熊排成一排！幸运的是，尽管他年纪尚小，但他非常清楚其中的危险。因此，他想知道总共有多少种安全的泰迪熊排列方式。问题随之而来——他自己无法计算出来……请做一个好伙伴，写一个程序来帮助他！

编写一个程序，完成以下任务：

• 从标准输入读取每种类型泰迪熊的数量；
• 计算安全排列泰迪熊的方法总数，结果对 $1\,000\,000$ 取模；
• 将结果写入标准输出。

输入格式

标准输入的唯一一行包含四个非负整数：$n_{A_1}, n_{A_2}, n_{B_1}, n_{B_2}$，以空格分隔（$0 \le n_{A_1}, n_{A_2}, n_{B_1}, n_{B_2} \le 38$）。它们分别表示模型 $A_1, A_2, B_1, B_2$ 的泰迪熊数量。泰迪熊的总数始终为正数。

输出格式

在标准输出的唯一一行中，输出安全排列泰迪熊的方法总数，对 $1\,000\,000$ 取模。

样例

输入 1

0 1 2 1

输出 1

6

说明 1

这 6 种安全的泰迪熊排列方式为：$B_1$ $A_2$ $B_1$ $B_2$、$B_1$ $A_2$ $B_2$ $B_1$、$B_2$ $A_2$ $B_1$ $B_1$、$B_2$ $B_1$ $A_2$ $B_1$、$B_1$ $B_2$ $A_2$ $B_1$ 以及 $B_1$ $B_1$ $A_2$ $B_2$。