Byteotian company 0101010 produces toys for children. 0101010 is well known, and their toys are considered top quality. To their horror, the employees have noticed that the four most recent models of teddies: $A_1$, $A_2$, $B_1$ and $B_2$ have a latent defect: should we take three teddies which all have the same letter in their model designations, or all have the same digit in their model designations, and line them up next to one another, the teddies will suffer an irreparable damage.

We shall say teddies are safely lined up, if none of them will suffer damage due to the latent defect, i.e. no three consecutive teddies have the same letter in their model designations, nor the same digit.

Byteasar has a collection of teddies, in which there are only the feral models - he has grown up to play with teddies only just, you see. To make things worse, Byteasar plays with his teddies by lining them up! Fortunately, despite his young age, he is well aware of the danger. Thus he wonders, how many safe line-ups of teddies are possible at all. And that's where the problems start - he is unable to determine it all by himself... Be a good mate and write a programme to help him!

Write a programme which:

• reads from the standard input the numbers of teddies of each type,
• calculates the number of safe line-ups of the teddies, modulo $1\,000\,000$,
• writes the result to the standard output.

Input

In the first and only line of the standard input there are four non-negative integers: $n_{A_1}$, $n_{A_2}$, $n_{B_1}$, $n_{B_2}$, separated by single spaces ($0 ≤ n_{A1},n_{A2},n_{B1},n_{B2} ≤ 38$). They denote the numbers of teddies, of models $A_1$, $A_2$, $B_1$ and $B_2$, respectively. The total number of teddies will always be positive.

Output

In the first and only line of the standard output your programme should write the number of safe line-ups of teddies, modulo $1\,000\,000$.

Example

Input

0 1 2 1

Output

6

Hints

The 6 safe line-ups of teddies are: $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$ and finally $B_1$ $B_1$ $A_2$ $B_2$.