메뉴 건너뛰기

문제


시간메모리제출 회통과 회비율
1초128MB
0
0
0.0%
나의 횟수나의 판정시도 명성공 명비율
00
0.0%
문제

타로 군이 사는 JOI 시는 남북으로 곧게 난 도로 \(a\)개와 동서로 곧게 난 도로 \(b\)개가 바둑판처럼 교차한다. 남북 도로는 서쪽에서부터 \(1, 2, \ldots, a\), 동서 도로는 남쪽에서부터 \(1, 2, \ldots, b\)이다. 서쪽에서 \(i\)번째 남북 도로와 남쪽에서 \(j\)번째 동서 도로가 만나는 교차점을 \((i, j)\)로 쓴다.

타로 군은 교차점 \((1, 1)\) 근처에 살고, 교차점 \((a, b)\) 근처 JOI 고등학교에 자전거로 다닌다. 자전거는 도로를 따라서만 움직이며, 동쪽으로나 북쪽으로만 간다.

지금 \(n\)개 교차점 \((x_1, y_1), \ldots, (x_n, y_n)\)에서 공사를 하고 있어 그 교차점은 지나갈 수 없다. \((1, 1)\)에서 \((a, b)\)까지 공사 교차점을 피하며 동쪽 또는 북쪽으로만 가는 경로의 수 \(m\)을 구하는 프로그램을 작성하라.

입력

입력은 다음 형식으로 주어진다.

\(a\) \(b\)

\(n\)

\(x_1\) \(y_1\)

\(\vdots\)

\(x_n\) \(y_n\)

  • 첫째 줄에 남북 도로 수 \(a\)와 동서 도로 수 \(b\)가 공백 하나로 구분되어 주어진다.
  • 둘째 줄에 공사 중인 교차점 수 \(n\)이 주어진다.
  • 다음 \(n\)줄에 공사 교차점의 \(x_i\), \(y_i\)가 공백 하나로 구분되어 주어진다.
  • \(1 \le a, b \le 16\)
  • \(1 \le n \le 40\)
  • \(1 \le x_i, y_i \le 16\)
  • 입력되는 값은 모두 정수이다.
출력

다음 형식으로 출력한다.

첫째 줄에 경로의 수 \(m\)을 출력한다.

예시 1
입력
5 4 3 2 2 2 3 4 2
출력
5
설명

\(a=5\), \(b=4\)이고 공사 교차점이 \((2,2)\), \((2,3)\), \((4,2)\)일 때 경로는 5가지이다.

위로