#AT25. Grid 2

Grid 2

[Y] Grid 2(dp_y)

来源: AtCoder Educational DP Contest - Problem Y 原题时限:2 秒 / 内存:1024 MB

题目描述

有一个 HH 行 WW 列的网格。记第 ii 行第 jj 列的格子为 (i,j)(i, j)。

网格中有 NN 个格子 (r1,c1),(r2,c2),…,(rN,cN)(r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N) 是墙,其余格子全部是空地。保证格子 (1,1)(1, 1) 与 (H,W)(H, W) 是空地。

太郎从格子 (1,1)(1, 1) 出发,每次只能向右或向下移动到相邻的空地,最终到达格子 (H,W)(H, W)。

求从 (1,1)(1, 1) 到 (H,W)(H, W) 的路径数,对 109+710^9 + 7 取模。

输入格式

输入由标准输入按以下格式给出:

H W N
r_1 c_1
r_2 c_2
:
r_N c_N

输出格式

输出路径数对 109+710^9 + 7 取模的结果。

数据范围

  • 2≤H,W≤1052 \le H, W \le 10^5
  • 1≤N≤30001 \le N \le 3000
  • 1≤ri≤H1 \le r_i \le H
  • 1≤ci≤W1 \le c_i \le W
  • 所有 (ri,ci)(r_i, c_i) 两两不同。
  • 格子 (1,1)(1, 1) 与 (H,W)(H, W) 为空地。

样例 1

输入:

3 4 2
2 2
1 4

输出:

3

样例 2

输入:

5 2 2
2 1
4 2

输出:

0

样例 3

输入:

5 5 4
3 1
3 5
1 3
5 3

输出:

24

样例 4

输入:

100000 100000 1
50000 50000

输出:

123445622