곰 인형

한 유명 장난감 회사가 어린이용 곰 인형을 만듭니다. 모델은 A1, A2, B1, B2 네 가지이며, 각 모델 이름은 알파벳 한 글자(A 또는 B)와 숫자 한 개(1 또는 2)로 이루어집니다.

최근 이 회사는 숨은 결함을 발견했습니다. 모델 이름의 알파벳이 같은 곰 인형 세 개, 또는 모델 이름의 숫자가 같은 곰 인형 세 개를 한 줄에 나란히 놓으면 그 세 인형이 모두 돌이킬 수 없이 망가집니다.

곰 인형을 한 줄로 세웠을 때, 연속한 세 인형이 같은 알파벳을 갖지도 않고 같은 숫자를 갖지도 않으면 그 줄을 안전한 줄이라고 합니다.

Byteasar는 이 곰 인형들을 모았고, 한 줄로 세우기를 좋아합니다. 각 모델의 곰 인형이 몇 개씩 있는지 주어질 때, 만들 수 있는 서로 다른 안전한 줄의 개수를 구하세요. 같은 모델의 곰 인형은 서로 구별하지 않습니다. 개수가 매우 클 수 있으므로 1,000,000으로 나눈 나머지를 출력합니다.

한 줄에 네 개의 음이 아닌 정수 $n_{A1}$, $n_{A2}$, $n_{B1}$, $n_{B2}$가 공백 하나로 구분되어 주어집니다 ($0 \le n_{A1}, n_{A2}, n_{B1}, n_{B2} \le 38$). 각각 모델 A1, A2, B1, B2의 곰 인형 개수를 뜻합니다. 곰 인형의 총 개수는 항상 1개 이상입니다.

안전한 줄의 개수를 1,000,000으로 나눈 나머지를 한 줄에 출력합니다.

$n_{A1}=0$, $n_{A2}=1$, $n_{B1}=2$, $n_{B2}=1$일 때 안전한 줄은 다음 여섯 가지입니다: B1 A2 B1 B2, B1 A2 B2 B1, B2 A2 B1 B1, B2 B1 A2 B1, B1 B2 A2 B1, B1 B1 A2 B2.