택배 기사는 격자 도시의 출발점 \((0,0)\) 에서 목적지 \((X,Y)\) 까지 배달을 가야 한다. 한 번에 오른쪽 (\(x\) 가 \(1\) 증가) 또는 위쪽 (\(y\) 가 \(1\) 증가) 으로만 이동할 수 있다.

그런데 좌표 \((P,Q)\) 에는 공사 구간이 있어 그 지점은 지날 수 없다. 공사 구간을 피해 출발점에서 목적지까지 가는 서로 다른 경로의 수를 구하여라.

경로의 수가 매우 클 수 있으므로 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 출력한다.

• \(0 \le X, Y \le 100{,}000\)
• \(0 \le P \le X\), \(0 \le Q \le Y\)
• 공사 구간이 출발점이나 목적지와 같을 수도 있다.

첫째 줄에 목적지 좌표 \(X\), \(Y\) 가 주어진다.

둘째 줄에 공사 구간 좌표 \(P\), \(Q\) 가 주어진다.

공사 구간을 지나지 않는 경로의 수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 한 줄에 출력한다.

riseoj 작성

출처 Original