题目描述

本题和 easy version 的唯一区别就是 k 的范围不同

小 i 来到了一个 $n \ imes m$ 的棋盘上，小 $i$ 想要从棋盘的最左上角（第 $1$ 行第 $1$ 列）走到棋盘的最右下角（第 $n$ 行第 $m$ 列），受到某种神奇的力量的影响，小 i 只能向右或者向下走，我们用 $(x, y)$ 来表示第 $x$ 行第 $y$ 列，那么小 i 位于坐标 $(x, y)$ 时下一步可以走到 $(x + 1, y)$ 或者 $(x, y + 1)$，小 i 想知道他从起点走到终点的方案数是多少。

这个问题真是太简单了！所以小 i 给自己设立了一些限制，小 i 规定棋盘上有一些格子是自己不能走的，小 i 想知道在这种情况下他从起点走到终点的方案数是多少。

由于答案可能很大，只需要输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含三个整数 $n, m, k$ 分别代表棋盘行数，棋盘列数和小 i 不能走的格子数量。

接下来包含 $k$ 行，每行两个整数 $r, w$ 代表小 i 不能经过第 $r$ 行第 $w$ 列的格子。

$1 \\leq n, m \\leq 10^5$

$0 \\leq k \\leq 10^3$

$1 \\leq r \\leq n, 1 \\leq w \\leq m$

数据保证不能通行的点不包括起点和终点，并且各不相同。

输出格式

输出包含一个整数代表答案对 $10^9 + 7$ 取模后的结果。

样例

5 6 1 
2 2

56

5 6 2 
1 3 
3 1

70

100000 100000 0 

691090292