31630번 - 가지밭길

문제

세로 길이가 $R,ドル 가로 길이가 $C$인 직사각형 격자 모양의 가지밭이 있습니다. 거리가 1ドル$인 두 격자점 간에는 두 점을 잇는 선분 형태의 길이 있습니다. 밤고는 매일 출근을 위해 왼쪽 위의 점 $(0, 0)$에서 시작하여 오른쪽 아래의 점 $(R, C)$으로 정확히 $R+C$개의 길을 따라 이동합니다. 격자점 중 몇 곳에는 귀여운 가지가 심겨 있어서 이 점들은 지나가지 않습니다.

매일 같이 이 밭을 오가던 밤고는 밭을 가로지르는 경로 중 어떤 것들은 사실상 같다고 생각합니다. 밤고가 이동한 경로를 따라 격자를 두 영역으로 잘라내면 일부는 위쪽 영역에 있고 나머지는 아래쪽 영역에 있습니다. 이때 두 경로에 대해 각 가지가 위쪽에 속하는지 아래쪽에 속하는지가 완전히 일치하면 두 경로는 같은 것입니다. 밤고의 생각에 서로 다른 경로는 몇 개가 있을까요?

잘라낸 두 영역에 대한 정확한 정의는 노트를 참고해 주세요.

입력

첫 번째 줄에 세 정수 $R,ドル $C,ドル $K$가 공백으로 구분되어 주어집니다. $R,ドル $C$는 각각 직사각형 격자의 세로, 가로의 길이이고, $K$는 심겨 있는 가지의 수입니다. $(1 \le R, C, K \le 5,000円)$

다음 $K$개 줄 각각에 심겨 있는 가지의 위치 $(r, c)$를 나타내는 정수 $r,ドル $c$가 공백으로 구분되어 주어집니다. $(0 \le r \le R; 0 \le c \le C)$

가지의 좌표는 모두 다르며, $(0, 0)$과 $(R, C)$에는 가지가 심겨 있지 않습니다.

출력

첫 번째 줄에, 밤고의 생각에 서로 다른 경로의 수를 소수 1ドル,000円,000円,007円 = 10^9+7$로 나눈 나머지를 출력합니다.

제한

노트

격자를 나누는 두 영역이 어떻게 정의되는지 더 엄밀하게 적으면 다음과 같습니다.

• 밤고가 이동한 경로가 $(R ,0)$을 지나면, 위쪽 영역은 전체집합, 아래쪽 영역은 공집합입니다.
• 그렇지 않고 경로가 $(0, C)$을 지나면, 아래쪽 영역은 전체집합, 위쪽 영역은 공집합입니다.
• 두 경우가 아니면, $(R, 0)$을 포함하는 영역을 아래쪽 영역, $(0, C)$을 포함하는 영역을 위쪽 영역이라고 부릅니다.