P3448 [POI 2006] MIS-Teddies

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$.

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 a single integer, the number of safe arrangements modulo $1\,000\,000$.

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