AT_s8pc_1_d.square1001の通学経路 (square1001's School Road)

square1001 每天步行去中学上学。

他住在左下角的交叉点 $(1,1)$，学校在右上角的交叉点 $(W,H)$。

不过，有如下条件：

• 为了节省时间，他只能向右或向上走。
• 这一天，他有 $K$ 个格子有事要办。
  每个有事的格子左下角为 $(X_i,Y_i)$，右上角为 $(X_i+1,Y_i+1)$。因此，对于每个有事的格子，他必须经过该格子四个角的交叉点中的至少一个。

请计算满足上述条件的走法有多少种。答案对 $1,000,000,007$ 取模。

输入从标准输入按以下格式给出。

$H$ $W$ $K$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_K$ $Y_K$

• 第 $1$ 行包含三个整数 $H\ (1 \leq H \leq 1,000)$，$W\ (1 \leq W \leq 1,000)$，$K\ (1 \leq K \leq 200)$，以空格分隔。
• 接下来的 $K$ 行，每行包含两个整数 $X_i\ (1 \leq X_i < W)$，$Y_i\ (1 \leq Y_i < H)$，以空格分隔。

请输出满足条件的走法数，输出一行。

样例解释 1

像 $(1,1)→(1,2)→(1,3)→(1,4)→(2,4)→(3,4)→(4,4)$ 这样的走法，以及 $(1,1)→(2,1)→(3,1)→(4,1)→(4,2)→(4,3)→(4,4)$ 这样的走法都不可以。因此，$20-2=18$，输出 $18$。
※图片左上角的数字缺失，敬请谅解。

由 ChatGPT 4.1 翻译