다람쥐와 도토리
우측 버튼을 눌러 기기를 연결해주세요.
문제정보
다람쥐와 도토리
100
참여자
8
정답률
37.5%
1
0

문제


한 다람쥐가 도토리를 찾아 숲 속을 뒤지고 있었습니다. 그러던 도중 저 멀리에 도토리 하나가 놓여있는 것을 발견했습니다. 다람쥐는 얼른 가서 주우려고 하다가 문득 이 근처에 함정을 파놓는 사냥꾼이 있다는 소문을 떠올렸습니다. 그래서 일단 주변을 꼼꼼하게 살펴보기로 했습니다. 열심히 살펴본 결과, 함정이 1개 있고 그 위치도 알아내는 데 성공합니다.

다람쥐는 여기서 시간을 지체하다간 사냥꾼이 언제 등장할지 모르니 일단 서둘러 함정을 피해 도토리를 줍고 도망가기로 합니다. 이 상황을 한번 2차원 좌표를 통해 나타내봅시다. 다람쥐는 현재 (0, 0)에 있고 도토리는 (), 함정은 (), 그리고 도망가고자 하는 최종 위치는 (N, M)입니다. 다람쥐는 x 좌표가 0보다 작거나 N보다 큰 곳에 위치할 수 없고, y 좌표도 0보다 작거나 M보다 큰 곳에 위치할 수 없습니다. 여기서 최단경로로 함정을 피해 도토리를 줍고 최종 위치에 가는 경우의 수는 총 몇 가지가 될까요?


입력


첫째 줄에 최종 위치를 나타내는 좌표 N과 M이 주어집니다.
(단, )

둘째 줄에 도토리의 위치를 나타내는 좌표 ()가 주어집니다.

셋째 줄에 함정의 위치를 나타내는 좌표 ()가 주어집니다.

도토리 및 함정의 x좌표는 N보다 작고, y좌표는 M보다 작습니다. 또한 다람쥐의 현재 위치 (0, 0)에는 도토리나 함정이 없습니다.


출력


함정을 피해 도토리를 줍고 최종 위치에 최단 경로로 도달하는 경우의 수를 1,000,000,007로 나눈 나머지를 출력합니다.


입/출력 예시
:
공백
:
줄바꿈
:
예시 1
입력
35
11
24
출력
14
예시 2
입력
1015
913
66
출력
1159620
예시 3
입력
46511
911
530
출력
512190602
예시 4
입력
14791841967877
1061926336977
188641259372
출력
796242484
⋇ 입출력 형식을 잘 지켜주세요
Q&A
누구나 질문하고 답변할 수 있는 Q&A입니다. 문제를 풀며 어려웠던 부분에 대해 질문해보세요.
이 문제에 관한 질문 (0)