问题
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