题目描述

在一个由 $n\times m$ 个方格构成的图中，有 $k$ 个方格是禁止进入的。请计算从左上角 $(1,1)$ 出发，每步朝右方或下方移动，不经过禁入的方格，最后到达右下角 $(n,m)$ 的路径条数。由于答案很大，输出模 $1,000,000,007$ 的余数。

输入格式

• 第一行：三个整数表示 $n$，$m$ 与 $k$。
• 第二行到第 $k+1$ 行：第 $i+1$ 行表示一个禁入方格的坐标 $(x_i,y_i)$。保证 $(x_i,y_i)$ 不会等于 $(1,1)$ 或 $(n,m)$，也不会有一个坐标重复出现两次。

输出格式

• 单个整数：表示路径数模 $1,000,000,007$ 的余数。

2 2 2
2 1
1 2

0

100000 100000 4
50001 50001
50000 50000
50000 50001
50001 50000

999612315

数据范围

• 对于 $30\%$ 的数据，$0\leq k\leq 200$；
• 对于 $60\%$ 的数据，$0\leq k\leq 1500$；
• 对于 $100\%$ 的数据，$0\leq k\leq 3000$；
• $1\leq n,m\leq 10^5$。