담벼락 이동하기 [2887 / 0B47]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 387   Total Tried : 825

---

The Champion of this Problem (C++) : gs20084 - ms / 401byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

송죽마을에는 벽돌로 이루어진 커다란 담벼락이 있다.

담벼락의 크기는 가로축에 놓인 벽돌의 최대 개수 W, 세로축에 놓인 벽돌 개수 H개로 아래와 같은 모양으로 되어 있다.

W(6) H(7) 모양의 담벼락


경곽이는 담벼락의 임의의 시작지점 S(s₁, s₂)에서 목표지점 G(g₁, g₂)로 이동할 수 있는 방법의 수를 알고 싶다.

경곽이는 아래와 같은 방법으로 다른 벽돌로 이동할 수 있으며, 벽돌이 없는 곳으로는 이동할 수 없다.



(담벼락 임의의 벽돌위치에서 인접한 벽돌로 이동할 때는 인접한 오른쪽, 왼쪽 상단, 오른쪽 상단 세가지 방향으로만 이동할 수 있다.)

시작지점 S에서 목표지점 G로 이동하는 서로 다른 방법의 개수를 출력하는 프로그램을 작성하시오.

Input

첫줄에는 담벼락의 크기 1<=W, H<=10가 공백을 기준으로 주어진다.
두 번째 줄에는 시작지점 좌표 s₁, s₂와 목표지점 좌표 g₁, g₂가 공백을 기준으로 주어진다.

Output

시작지점 S에서 목표지점 G로 이동하는 서로 다른 방법의 개수를 출력한다.

IO Example

Input
6 7
2 3 6 7

Output
878

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python3]
Prob Analysis : [Problem Statistics] | [Solution]

---