아몬드 초콜릿
시간 제한2초메모리 제한1024 MB
변의 길이가 정수인 등각 육각형에서 모서리 여섯 곳을 이미 덮은 상태로, 나머지 부분을 단위 정삼각형 두 개짜리 마름모로 채우는 방법의 수를 구합니다.
문제
한별이네 초콜릿 가게는 밸런타인데이 특별 상품으로 육각형 초콜릿 위에 아몬드를 얹은 아몬드 초콜릿을 팔려고 한다. 육각형 초콜릿의 내각은 모두 도이고, 각 변의 길이는 정수이다. 아몬드 하나는 한 변의 길이가 인 정삼각형 두 개를 변끼리 붙인 모양이다. 아몬드들은 서로 겹치지 않아야 하며, 초콜릿 밖으로 벗어나지 않으면서 초콜릿 전체를 덮어야 한다.
아몬드 초콜릿을 예쁘게 보이도록, 한별이는 육각형의 각 꼭짓점을 포함하는 두 삼각형을 덮도록 아몬드 6개를 이미 배치해 두었다.
초콜릿의 나머지 부분을 채우는 방법의 수를 구하라.
입력
첫 번째 줄에 육각형 초콜릿의 각 변의 길이를 나타내는 정수 6개 가 시계 방향 순서로 공백을 두고 주어진다. 주어지는 입력은 올바른 육각형을 이룬다.
출력
첫 번째 줄에 문제의 정답을 로 나눈 나머지를 출력한다.