方格路径（三）(Grid Paths III)

题目描述

在一个由 $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$ 的余数。

样例输入 #1

2 2 2
2 1
1 2

样例输出 #1

0

样例输入 #2

100000 100000 4
50001 50001
50000 50000
50000 50001
50001 50000

样例输出 #2

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$。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐。

测试点分布