격자 이동하기

동우는 $\\left(a,b\\right)$ 크기의 특수한 2차원 격자 위에 살고 있다. 이 격자에서 모든 정수 좌표 $\\left( x,y \\right)$는 상하좌우로 인접한 좌표와 길이 $1$인 길로 연결되어 있다. 또한 일부 좌표에는 $\\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(5000,ab)$).

이후 $N$개의 줄에 대각선 길이 있는 정수 좌표 $(x_i,y_i)$가 공백으로 구분되어 주어진다. 이는 $(x_i,y_i)$와 $(x_i+1,y_i+1)$ 사이에 길이 있음을 뜻한다. 같은 좌표는 여러 번 주어지지 않는다.

동우가 이동할 수 있는 최단 경로의 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다. 단, $10^9+7$은 소수이다.