헨젤과 그레텔의 계모는 아이들을 숲속에 버리기로 계획했다.

그녀의 계획을 듣게 된 헨젤과 그레텔은 집으로 가는 길을 표시하기 위해 하얀 조약돌을 \(A\)개 모았다.

계모가 아이들을 데리고 숲속 깊이 들어가는 동안 아이들은 하얀 조약돌을 하나씩 흘렸다. (헨젤과 그레텔은 같은 위치에 조약돌을 중복으로 흘리지 않는다.)

숲을 이차원 좌표평면으로 표현하자면 현재 헨젤과 그레텔의 위치는 \((1, 1)\) 좌표에 해당하고, 그들의 집은 \((N, M)\) 좌표에 해당한다.

숲에는 바위나 나무 등으로 인해 이동이 불가능한 위치(장애물)가 \(B\)개 존재한다. (이동이 불가능한 위치는 서로 중복되지 않는다.)

아이들은 길을 잃지 않기 위해 오직 동쪽(\(X\)좌표가 증가하는 방향) 혹은 남쪽(\(Y\)좌표가 증가하는 방향)으로만 이동한다.

하얀 조약돌을 모두 회수하고 집에 돌아오는 경우의 수를 출력하시오.

• \(1 \le N, M \le 100\)
• \(1 \le A\) (하얀 조약돌의 개수)
• \(0 \le B\) (장애물의 개수)
• 모든 좌표 \((X, Y)\)는 \(1 \le X \le N\), \(1 \le Y \le M\)을 만족한다.
• 하얀 조약돌의 위치는 서로 중복되지 않으며, 장애물의 위치도 서로 중복되지 않는다.

첫째 줄에 숲의 세로 크기 \(N\), 가로 크기 \(M\), 하얀 조약돌의 개수 \(A\), 장애물의 개수 \(B\)가 공백으로 구분되어 주어진다.

다음 \(A\)개의 줄에 각 하얀 조약돌의 위치를 나타내는 두 정수 \(X\), \(Y\)가 주어진다.

이어서 다음 \(B\)개의 줄에 각 장애물의 위치를 나타내는 두 정수 \(X\), \(Y\)가 주어진다.

첫째 줄에 하얀 조약돌을 모두 회수하면서 \((1, 1)\)에서 출발해 \((N, M)\)에 도착하는 경우의 수를 출력한다.

이때 경우의 수가 \(21\)억(\(2\,100\,000\,000\)) 이하임이 보장된다.

rip 작성

출처 지정되지 않음