Description

Byteoian is a company specializing in children's toys. Their products are of high quality and well received.

However, it was recently discovered that their teddy bears have a fatal flaw. There are four models of teddy bears: $A1$, $A2$, $B1$, $B2$. If three teddy bears with the same letter or the same digit are placed together, it will cause fatal damage.

An arrangement of teddy bears is called safe if there are no three consecutive teddy bears with the same letter or the same digit.

You have collected some teddy bears and want to know how many safe arrangements in a row of all these teddy bears exist. Since the number of safe arrangements can be large, output the result modulo $1\,000\,000$.

Input Format

The input contains four integers: $n_{A1}, n_{A2}, n_{B1}, n_{B2}$, which denote the numbers of type $A1$, $A2$, $B1$, and $B2$ teddy bears, respectively.

Output Format

Output a single integer, the number of safe arrangements modulo $1\,000\,000$.

0 1 2 1

6

Hint

Constraints: $0 \leq n_{A1}, n_{A2}, n_{B1}, n_{B2} \leq 38$.

Translated by ChatGPT 5