시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3662117567329.505%

문제

세준이는 크기가 N*M인 직사각형 도시에 살고 있다. 또, 세준이의 집은 (1, 1)에 있고, 학원은 (N, M)에 있고, 오락실이 C개 있다.

세준이의 현재 위치가 (r, c) 일 때, (r+1, c) 또는 (r, c+1)로만 이동할 수 있다. 오락실을 방문할 때는 규칙이 하나 있는데, 오락실 번호가 증가하는 순서대로 가야한다는 것이다. 2번 오락실을 먼저 가고, 그 후에 1번 오락실을 가면 안 되고, 2번 오락실을 가려면, 그 전에 아무 오락실도 가지 않거나, 1번 오락실을 방문했을 때만 가능하다.

세준이는 오락실을 K번 방문해서 학원에서 도착하는 경로의 경우의 수가 궁금해지기 시작했다. 오락실을 0개 방문했을 때부터, C개 방문했을 때 까지 경우의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N M C가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, C는 50보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 C개의 줄에 1번 오락실부터 C번 오락실까지 위치가 차례대로 주어진다. 오락실의 위치가 중복되는 경우는 없지만, 오락실의 위치가 (1,1) 또는 (N,M)일 수도 있다.

출력

첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3 3 2
2 2
3 2

예제 출력 1

1 3 2
  • 0개: (1,1) → (1,2) → (1,3) → (2,3) → (3,3)
  • 1개: (1,1) → (2,1) → (2,2) → (2,3) → (3,3), (1,1) → (1,2) → (2,2) → (2,3) → (3,3), (1,1) → (2,1) → (3,1) → (3,2) → (3,3)
  • 2개: (1,1) → (2,1) → (2,2) → (3,2) → (3,3), (1,1) → (1,2) → (2,2) → (3,2) → (3,3)

예제 입력 2

6 4 2
5 3
3 2

예제 출력 2

14 24 0

예제 입력 3

5 5 3
1 3
2 4
3 5

예제 출력 3

42 14 10 4

예제 입력 4

50 50 2
50 50
1 1

예제 출력 4

0 0 0

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: deunlee, haja
  • 잘못된 조건을 찾은 사람: doju