꿀벌 승연이
면접 대비시간 제한1초메모리 제한1024 MB
N×M 육각 격자에서 (1,1)에서 (N,M)까지 아래, 오른쪽 위, 오른쪽 아래 방향으로만 이동하며 K개의 구멍 칸을 피해 가는 경로의 수를 10^9+7로 나눈 나머지를 구한다.
문제
이세계의 승연이는 꿀벌이다.
승연이가 사는 벌집은 조금 특이한 구조로 되어 있다. 벌집은 (N)행 (M)열의 격자로 이루어져 있고, 각 칸은 정육각형 모양이다. 같은 행에 있는 두 칸을 비교하면, 짝수 번째 열의 칸은 홀수 번째 열의 칸보다 반 칸 아래에 있다. 아래 그림은 3행 4열 격자로 이루어진 벌집의 예시이다.
두 육각형 칸이 하나의 변을 공유하면 서로 인접하다고 한다. 육각형 칸의 각 변에는 인접한 칸으로 이동할 수 있는 문이 있는데, 벌집 내 교통 정리를 위해 각 칸에서는 아래쪽, 오른쪽 위, 오른쪽 아래 칸으로만 이동할 수 있다. 또, 벌집에는 구멍 칸이 있을 수도 있는데, 구멍 칸으로는 이동할 수 없다.
승연이는 최근 꿀벌들 사이에 급속도로 전염되고 있는 변이 바이러스를 피해 벌집콕 생활을 하고 있다. 심심함이 극에 달한 승연이는 벌집의 (1)행 (1)열 칸에서 (N)행 (M)열 칸까지 바깥으로 나가지 않고 이동하는 경로의 개수가 알고 싶어졌다.
자가 격리 중인 승연이가 더 이상 답답하지 않도록 경로의 개수를 세어 알려주자!
입력
첫째 줄에 (N), (M)이 공백으로 구분되어 주어진다.
다음 줄에는 구멍 칸의 개수 (K)가 주어진다.
이어서 (K)개 줄에 구멍 칸의 정보 (x_i), (y_i)가 공백으로 구분되어 주어진다. 이는 (i)번째 구멍 칸이 (x_i)행 (y_i)열에 있음을 뜻한다. 모든 구멍 칸의 위치는 서로 다르다.
(1)행 (1)열 칸 또는 (N)행 (M)열 칸이 구멍인 경우는 없음이 보장된다.
출력
벌집의 (1)행 (1)열 칸에서 (N)행 (M)열 칸으로 이동하는 경로의 개수를 (10^9+7)로 나눈 나머지를 출력한다.
제한
- 2 ≤ (N) ≤ 1,000
- 2 ≤ (M) ≤ 1,000
- 0 ≤ (K) ≤ min((NM) - 2, 104)
- 1 ≤ (x_i) ≤ (N)
- 1 ≤ (y_i) ≤ (M)