← 返回题目列表

AtCoder · dp_y

Y. 网格 2

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

有一个网格 H 水平行和 W 垂直列。 让 (i, j) 表示 i从顶部开始的第行和 j左起第 列。

在网格中, N 正方形 (r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N) 是墙方格,其他都是空方格。 保证正方形 (1, 1) 和 (H, W) 是空方块。

太郎将从广场开始 (1, 1) 并达到 (H, W) 通过重复向右或向下移动到相邻的空方块。

从 Square 中找出太郎的路径数 (1, 1) to (H, W),模数 10^9 + 7.

约束

  • 输入中的所有值都是整数。
  • 2 \leq H, W \leq 10^5
  • 1 \leq N \leq 3000
  • 1 \leq r_i \leq H
  • 1 \leq c_i \leq W
  • 正方形 (r_i, c_i) 都是不同的。
  • 正方形 (1, 1) 和 (H, W) 是空方块。

输入

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

H W N
r_1 c_1
r_2 c_2
:
r_N c_N

输出

打印 Square 中 Taro 的路径数 (1, 1) to (H, W),模数 10^9 + 7.


示例输入 1

3 4 2
2 2
1 4

示例输出 1

3

共有以下三个路径:


示例输入 2

5 2 2
2 1
4 2

示例输出 2

0

可能没有路径。


示例输入 3

5 5 4
3 1
3 5
1 3
5 3

示例输出 3

24

示例输入 4

100000 100000 1
50000 50000

示例输出 4

123445622

请务必打印模数计数 10^9 + 7.