23083번 - 꿀벌 승연이

이세계의 승연이는 꿀벌이다.

승연이가 사는 벌집은 조금 특이한 구조로 되어있다. 벌집은 \(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, 10⁴)
• 1 ≤ \(x_i\) ≤ \(N\)
• 1 ≤ \(y_i\) ≤ \(M\)