다람쥐와 도토리 - 구름LEVEL
다람쥐와 도토리
Press the right button to connect the device.
Quiz Info
다람쥐와 도토리
100points
Participant
7
Solved Rate
28.5%
0
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로 나눈 나머지를 출력합니다.


Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
35
11
24
Output
14
Example 2
Input
1015
913
66
Output
1159620
Example 3
Input
46511
911
530
Output
512190602
Example 4
Input
14791841967877
1061926336977
188641259372
Output
796242484
⋇ Please keep the input and output formats carefully
Q&A
누구나 질문하고 답변할 수 있는 Q&A 게시판입니다. 문제를 풀며 어려웠던 부분에 대해 질문해보세요.
Registered Questions (0)