[AdditionalFile5507.zip](file://AdditionalFile5507.zip?type=additional_file)

#5507. 「POI2006 R3」泰迪熊 Teddies

标签: 传统 | 时间限制: 14000 ms | 内存限制: 32 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – III etap Misie

字节公司 0101010 生产儿童玩具。0101010 是一家非常知名的公司，其玩具以坚固耐用而闻名。然而，公司的员工们惊恐地发现，最近的四款泰迪熊型号：$A1$、$A2$、$B1$ 和 $B2$ 有一个隐藏的缺陷：如果我们取出三只型号字母全部相同，或者型号数字全部相同，并将它们并排放在一行，那么这些泰迪熊将会受到不可逆转的损坏。

我们将一种泰迪熊的行内排列称为安全的，如果这种排列不会导致任何泰迪熊受损，也就是说，任意连续三只泰迪熊的型号字母不全部相同，型号数字也不全部相同。

Bajtazar 有一个只包含这些有缺陷型号的泰迪熊收藏。Bajtazar 玩这些泰迪熊时，会将它们排成一行。他想知道，有多少种可能的安全排列方式。请编写一个程序来帮助他确定这个数量。

请编写一个程序，实现以下功能：

• 从标准输入读取每种型号泰迪熊的数量，
• 计算将泰迪熊排成一行时的安全排列数量，结果对 $1000000$ 取模，
• 将结果输出到标准输出。

输入格式

输入的第一行且仅一行包含四个非负整数：$n_{A1}, n_{A2}, n_{B1}, n_{B2}$ $(0 \le n_{A1}, n_{A2}, n_{B1}, n_{B2} \le 38)$，由单个空格隔开。它们分别表示型号为 $A1$、$A2$、$B1$ 和 $B2$ 的泰迪熊的数量。你可以假设泰迪熊的总数是正数。

输出格式

在输出的第一行且仅一行，你的程序应输出将泰迪熊排成一行时的安全排列数量，结果对 $1000000$ 取模。

样例

输入

0 1 2 1

输出

6

存在 6 种正确的泰迪熊排列方式：$B1\ A2\ B1\ B2$，$B1\ A2\ B2\ B1$，$B2\ A2\ B1\ B1$，$B2 B1 A2 B1$，$B1\ B2\ A2\ B1$ 以及 $B1\ B1\ A2\ B2$。