31985번 - 체스판

문제

크기가 $N \times M$인 체스판이 있다. 체스판의 행 번호는 위에서부터 1,ドル 2, \cdots, N$이고, 열 번호는 왼쪽에서부터 1,ドル 2, \cdots, M$이다. 체스판의 각 칸은 $(i, j)$로 표현한다. 여기서, $i$는 행 번호, $j$는 열 번호이다. 그리고, 체스판에는 $K$개의 금지된 칸이 존재한다. 단, $(1,1)$과 $(N,M)$은 금지된 칸이 아니다.

말 $A,ドル $B$는 $(1,1)$에서 시작하여 다음의 규칙에 따라 동시에 한 칸씩 이동하며 $(N,M)$까지 가려고 한다.

1. 어떤 말이 현재 $(i,j)$에 있다면, 해당 말은 $(i+1,j)$ 또는 $(i,j+1)$으로 이동할 수 있다. 이 때, 말이 체스판을 벗어나는 이동은 허용하지 않는다.
2. 처음에 말 $A$는 $(1,1)$에서 $(1,2)$로 이동하며, 말 $B$는 $(1,1)$에서 $(2,1)$로 이동해야 한다.
3. 이동하는 과정에서 두 말은 $(1,1)$과 $(N,M)$를 제외하고 어떤 칸에서도 만나서는 안된다.
4. 어떤 말도 금지된 칸으로 이동할 수 없다.

이러한 규칙을 따르면서 말 $A,ドル $B$가 $(1,1)$에서 동시에 출발하여 $(N,M)$으로 도달할 수 있는 경로쌍의 개수를 구해보자. 말 $A$가 이동한 경로를 $a,ドル 말 $B$가 이동한 경로를 $b$라고 하면 조건을 만족하는 $(a,b)$의 개수를 구하면 된다.

입력

첫 번째 줄에는 체스판의 행 크기 $N,ドル 열 크기 $M,ドル 금지된 칸의 개수 $K$가 공백으로 구분되어 주어진다. $(2 \le N,M \le 1,000円,000円;$ 0ドル \le K \le min(N \times M-2,5,000円))$

두 번째 줄부터 $K + 1$번째 줄까지는 금지된 칸의 행 번호 $x,ドル 열 번호 $y$가 공백으로 구분되어 주어지며, 같은 칸은 두 번 이상 주어지지 않는다. $(1 \le x \le N;$ 1ドル \le y \le M;$ $(x,y) \neq (1,1);$ $(x,y) \neq (N,M))$

입력에서 주어지는 모든 수는 정수이다.

출력

말 $A,ドル $B$가 $(1,1)$에서 동시에 출발하여 $(N,M)$으로 도달할 수 있는 경로쌍의 개수를 10ドル^9 + 7$로 나눈 나머지를 출력한다.

제한

힌트