32391번 - 격자 이동하기

동우는 $\left(a,b\right)$크기의 특수한 $2$차원 격자 위에서 살고 있다. 이 격자에서 모든 정수 좌표 $\left( x,y \right)$는 상하좌우로 인접한 좌표와 길이 $1$인 길로 연결되어 있다. 또한, 특정 좌표들에서는 대각선으로도 이동할 수 있는 길이 있는데, 이 경우 $\left( x,y \right)$과 $\left( x+1,y+1 \right)$ 사이에 길이 $\sqrt{2}$인 길로 연결되어 있다.

동우는 원점 $\left( 0,0 \right)$에서 출발하여 길을 따라 목표 지점 $\left( a,b \right)$로 이동하려고 한다. 이때, 동우가 이동할 수 있는 최단 경로의 경우의 수를 구해보자.

첫 번째 줄에 목표 지점의 좌표 $(a,b)$를 나타내는 두 정수 $a,b(0\leq a,b\leq 10^6;$ $1\leq a+b)$가 공백으로 구분되어 주어진다.

두 번째 줄에 대각선 경로의 개수 $N(0\leq N\leq\min(5\, 000,a\cdot b))$이 주어진다.

세 번째 줄부터 $N$줄에 걸쳐 대각선 길이 존재하는 정수 좌표 $(x_i,y_i)$가 공백으로 구분되어 주어진다. 이는 $(x_i,y_i)$와 $(x_i+1,y_i+1)$ 사이에 길이 있음을 의미한다. 같은 좌표가 여러 번 주어지지 않는다.

동우가 이동할 수 있는 최단 경로의 경우의 수를 $10^9+7$로 나눈 나머지를 출력하라.

단, $10^9+7$은 소수이다.