题目描述

有一个 $n$ 行，$m$ 列的网格。

在网格中， $k$ 个方格为 $(r_1, c_1), (r_2, c_2), \ldots, (r_k, c_k)$ 个方格。方格 $(r_1, c_1), (r_2, c_2), \ldots, (r_k, c_k)$ 是墙方格，其他方格都是空方格。可以保证 $(1, 1)$ 和 $(n, m)$ 是空方格。

太郎将从方格 $(1, 1)$ 出发，通过反复向右或向下移动到相邻的空方格，到达 $(n, m)$ 。

求太郎从方格 $(1, 1)$ 到 $(n, m)$ 的路径数，取模 $10^9 + 7$ 。

输入格式

第一行输入 $n,m,k$ 。

接下来 $k$ 行，每行两个整数为 $r_i,c_i$。

输出格式

输出一个整数代表答案。

3 4 2
2 2
1 4

3

5 2 2
2 1
4 2

0

5 5 4
3 1
3 5
1 3
5 3

24

100000 100000 1
50000 50000

123445622

提示

数据范围

• $2\ \leq\ n,\ m\ \leq\ 10^5$
• $1\ \leq\ k\ \leq\ 3000$
• $1\ \leq\ r_i\ \leq\ n$
• $1\ \leq\ c_i\ \leq\ m$

样例 1 解释

有以下三条路径