토쟁이의 등굣길
시간 제한1초메모리 제한128 MB
주어진 토스트 가게를 지나 (1,1)에서 (w,h)까지 가는 최단 경로의 수를 1000007로 나눈 나머지를 구한다.
문제
인하대학교에 다니는 토쟁이는 y축과 평행한 도로 개와 x축과 평행한 도로 개가 놓인 도시에 산다. 도로가 만나는 지점은 좌표 로 나타내며, 왼쪽에서 번째 세로 도로와 아래에서 번째 가로 도로가 만나는 지점이다. 토쟁이의 집은 도시의 왼쪽 맨 아래인 에, 학교는 오른쪽 맨 위인 에 있다. 이웃한 두 교차점 사이를 이동하는 시간은 어느 구간이나 같다.
토쟁이는 매일 아침 등교하면서 토스트 가게에 들러 토스트를 사 먹는다. 늦장을 부리다가 수업 시작 시각에 딱 맞게 도착하도록 출발하므로, 집에서 토스트 가게를 거쳐 학교까지 가는 경로는 언제나 시간이 가장 적게 걸리는 경로여야 한다. 토스트를 만드는 시간과 먹는 시간은 0초로 본다.
아래 그림은 , 인 도시다.

토스트 가게가 에 있다면 집 에서 가게를 거쳐 학교 까지 가는 최소 시간 경로는 다음 두 가지다.

토스트 가게의 위치가 주어질 때, 토쟁이가 지각하지 않고 학교에 도착할 수 있는 등굣길이 몇 가지인지 구하라.
입력
첫째 줄에 y축과 평행한 도로의 개수 와 x축과 평행한 도로의 개수 가 공백으로 구분되어 주어진다. ()
둘째 줄에 토스트 가게의 좌표 와 가 공백으로 구분되어 주어진다. (, ) 와 는 정수다.
출력
첫째 줄에 등굣길의 개수를 1000007로 나눈 나머지를 출력한다.