← 返回题目列表

AtCoder · code_festival_2015_okinawa_g

G. 华丽的花瓶

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

问题

Cat Snuke 有一对花瓶。其中一个被标记为花瓶 1,另一个被标记为花瓶 2。一开始是花瓶 1 包含 A 蓝色的花朵和 B 红色的花朵。另外,蓝色花朵的数量大于或等于红色花朵的数量,换句话说, A ≧ B。另外,花瓶 2 为空,既不包含蓝色花朵也不包含红色花朵。

顺便说一句,Cat Snuke 不喜欢将特定数量的红色花朵与特定数量的蓝色花朵混合。这种组合称为 脏的放置 。有 N 总共有不同的脏位置, i_{th} 脏的放置 是精确的组合 p_i 蓝色的花朵和 q_i 红色的花朵。

猫 Snuke 想要移动花瓶里的所有花朵 1 到花瓶 2 一一。然而,Cat Snuke 必须遵守以下规则。

  • 花瓶用 1 和花瓶 2,蓝色花朵的数量应始终大于或等于红色花朵的数量。
  • 花瓶用 1 和花瓶 2,蓝色花朵的数量和红色花朵的数量的组合不能是任意的 脏的放置 (随时)。

按照上述规则,回答能移动花瓶中所有花朵的所有可能方法的数量 1 到花瓶 2,模数 1,000,000,007。请注意,所有颜色相同的花是无法区分的(相同)。


输入

输入将由以下格式的标准输入给出

A B N
p_1 q_1
p_2 q_2
:
p_N q_N
  • 对于第一行, A、B(1≦B≦A≦100,000)、N(0≦N≦20) 将用空格分隔。
  • 从第二行开始有 N 附加行给出所有脏布局。对于 i_{th} 行,整数 p_i(1≦p_i≦A)、q_i(1≦q_i≦B,q_i≦p_i) 将用空格分隔。

输出

请输出移动花瓶中所有花朵的所有可能方法的个数时的余数 1 到花瓶 2,模数 1,000,000,007.

在输出末尾打印换行符。


输入示例 1

3 1 0

输出示例 1

2

如下所示,移动花朵有两种可能的方式。

  • 移动顺序为,蓝色,蓝色,红色,蓝色。
  • 移动顺序为,蓝色,红色,蓝色,蓝色。

输入示例 2

7 5 3
4 2
6 1
5 4

输出示例 2

0

输入示例3

98765 43210 5
314 159
26535 8979
3238 46
26433 8327
950 288

输出示例 3

763788532