背景

啷个整起的哦，喊个师傅来修一下咩。

题目描述

机房可以看成是一个 $n \times m$ 的格点图。

师傅进门的位置为 $(1,1)$ ，在㮟㮟头打麻将的小伙子的位置为 $(n,m)$ 。

师傅穿的是皮孩，所以每步他能从 $(x,y)$ 走到 $(x+1,y)$ 或 $(x,y+1)$ 。

师傅也想来开一局，但是机房有 $K$ 块地皮翘起来了，走上去可能会拽筋斗，所以不能走。

请你求出师傅从 $(1,1)$ 走到 $(n,m)$ 的方案数，答案对 $10^9+7$ 取模。

输入

输入的第一行包含三个整数 $n, m, k\ (1\le n, m\le 10^5, 1 \le k \le 3\times 10^3)$ ，表示图的大小和不能走的格子数目。

接下来的 $k$ 行每一行都包含两个整数 $x_i, y_i$ ，表示第 $i$ 个不能走的格子是 $(x_i,y_i)$ ，输入数据保证坐标在格点图内部且互不相同。

输出

输出一行一个整数表示合法的方案数，答案对 $10^9+7$ 取模。

样例

3 4 2
2 2
1 4

3

5 5 4
3 1
3 5
1 3
5 3

24

100000 100000 1
50000 50000

123445622

来源

2025 UESTC ICPC Training for Dynamic Programming and Search