Teddies

A well-known toy company makes teddy bears for children. There are four models: A1, A2, B1, and B2. Each model name consists of one letter (A or B) and one digit (1 or 2).

The company recently found a latent defect. If three teddies whose model names share the same letter, or three teddies whose model names share the same digit, are placed next to one another in a row, all three are damaged beyond repair.

A row of teddies is safe if no three consecutive teddies share the same letter and no three consecutive teddies share the same digit.

Byteasar has collected these teddies and loves lining them up. Given how many teddies he owns of each model, count how many different safe rows he can form. Teddies of the same model are indistinguishable. Since the count can be large, output it modulo 1,000,000.

One line with four non-negative integers $n_{A1}$, $n_{A2}$, $n_{B1}$, $n_{B2}$, separated by single spaces ($0 \le n_{A1}, n_{A2}, n_{B1}, n_{B2} \le 38$). They are the numbers of teddies of models A1, A2, B1, and B2, respectively. The total number of teddies is always at least 1.

Print, on a single line, the number of safe rows modulo 1,000,000.

When $n_{A1}=0$, $n_{A2}=1$, $n_{B1}=2$, $n_{B2}=1$, the six safe rows are: B1 A2 B1 B2, B1 A2 B2 B1, B2 A2 B1 B1, B2 B1 A2 B1, B1 B2 A2 B1, and B1 B1 A2 B2.