题目描述

给定一个由 $h$ 行 $w$ 列个格子组成的矩阵。

我们用 $(i, j)$ 表示矩阵中第 $i$ 行第 $j$ 列的格子。

矩阵中的每个格子都有一个颜色 —— 黑色 或者 白色。

白色的格子是可以走到的，黑色的格子是不能走到的。

有 $n$ 个黑色的格子，且左上角和右下角的两个格子都为白色的格子。

你现在要从左上角的格子 $(1, 1)$ 走到右下角的格子 $(h,w)$。每次移动，你可以从当前格子移动到它右边或者下面相邻的格子，但是不能移动到黑色的格子，也不能移动到矩阵的边界外。

也就是说，如果你当前在格子 $(x, y)$：

• 你可以移动到格子 $(x, y+1)$ 当且仅当 $y+1 \le w$ 且 $(x, y+1)$ 是一个白色的格子；
• 你可以移动到格子 $(x+1, y)$ 当且仅当 $x+1 \le h$ 且 $(x+1, y)$ 是一个白色的格子。

求：有多少种不同的方案？

由于方案数可能很大，所以你只需要输出方案数模 $10^9 + 7$ 的结果即可。

输入格式

第一行，三个整数 $h, w, n(1 \le h,w \le 10^5, 1 \le n \le 2000)$，分别表示矩阵的行数、列数，以及黑色格子的数量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $r_i$ 和 $c_i$，表示第 $i$ 个黑色的格子的位置在 $(r_i, c_i)$（$1 \le r_i \le h, 1 \le c_i \le w$）。

数据保证每个格子的位置都不一样，且左上角和右下角的格子都是白色的格子。

输出格式

输出一个整数，表示从左上角移动到右下角的不同方案数模 $10^9 + 7$ 的结果。

样例

3 4 2
2 2
2 3

2

100 100 3
15 16
16 15
99 88

545732279

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$h, w \le 100, n \le 20$
• 对于 $60\%$ 的数据，$h, w \le 10^4, n \le 200$
• 对于 $100\%$ 的数据，$1 \le h, w \le 10^5, 1 \le n \le 2000$