AT_code_festival_2015_okinawa_g Gorgeous Vases

猫咪Snuke有一对花瓶。一个标记为花瓶$ 1 $，另一个标记为花瓶$ 2 $。最初，花瓶$ 1 $中有$ A $朵蓝花和$ B $朵红花。此外，蓝花的数量大于或等于红花的数量，即$ A \geq B $。另外，花瓶$ 2 $是空的，既没有蓝花也没有红花。 顺便说一下，猫咪Snuke不喜欢将特定数量的红花与特定数量的蓝花混合在一起。这样的组合被称为**脏位置（Dirty Placement）**。总共有$ N $种不同的脏位置，第$ i $种脏位置恰好包含$ p_i $朵蓝花和$ q_i $朵红花。 猫咪Snuke想把花瓶$ 1 $中的所有花一朵一朵地移到花瓶$ 2 $中。但是，猫咪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 \leq B \leq A \leq 100,000 $）、$ N $（满足条件 $ 0 \leq N \leq 20 $），它们之间用空格分隔。 - 从第二行开始，接下来的 $ N $ 行将给出所有的“Dirty Placements”（脏位置）。对于第 $ i $ 行（$ 1 \leq i \leq N $），将给出整数 $ p_i $（满足条件 $ 1 \leq p_i \leq A $）、$ q_i $（满足条件 $ 1 \leq q_i \leq B, q_i \leq p_i $），它们之间用空格分隔。

输出将所有花瓶1中的花移动到花瓶2中的所有可能方法的数量对1,000,000,007取模的余数。 在输出结束时打印一个新行。 ### 示例解释 1 如下所示，有两种可能的方法来移动花朵： - 移动顺序为：蓝，蓝，红，蓝。 - 移动顺序为：蓝，红，蓝，蓝。

### Problem Cat Snuke has a pair of vases. One is noted as vase $ 1 $, the other one is noted as vase $ 2 $. At first, the vase $ 1 $ contains $ A $ blue flowers and $ B $ red flowers. In addition, the number of blue flowers is larger than or equal to the number of red flower, in other words, $ A\ ≧\ B $. In addition, vase $ 2 $ is empty, contains neither blue flowers nor red flowers. By the way, Cat Snuke doesn’t like mixing a specific number of red flowers with a specific number of blue flowers. Such combination is called as a **Dirty Placement** . There are $ N $ different Dirty Placements in total, the $ i_{th} $ **Dirty Placement** is the combination of precisely $ p_i $ blue flowers and $ q_i $ red flowers. Cat Snuke wants to move all the flowers that are in vase $ 1 $ to vase $ 2 $ one by one. However, Cat Snuke has to follow the following rules. - For vase $ 1 $ and vase $ 2 $, the number of the blue flowers should always be larger than or equal to that of the red flowers. - For vase $ 1 $ and vase $ 2 $, the combination of the number of the blue flowers and the number of the red flowers must not be any **Dirty Placement** (at anytime). In accordance with the above rules, answer the number of all the possible methods that can move all the flower in vase $ 1 $ to vase $ 2 $, modulo $ 1,000,000,007 $. Please note that all the flowers with the same color are indistinguishable (identical). ### Sample Explanation 1 As shown below, there are two possible ways to move flowers. - The moving order is as, blue, blue, red, blue. - The moving order is as, blue, red, blue, blue.