AT_code_festival_2015_okinawa_g Gorgeous Vases

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-okinawa-open/tasks/code_festival_2015_okinawa_g

Inputs will be given by standard input in following format > $ A $ $ B $ $ N $ $ p_1 $ $ q_1 $ $ p_2 $ $ q_2 $ : $ p_N $ $ q_N $ - For the first line, $ A、B(1≦B≦A≦100,000) $、$ N(0≦N≦20) $ will be given divided by spaces. - From the second line there are $ N $ additional lines to give all the Dirty Placements. For the $ i_{th} $ line, integer $ p_i(1≦p_i≦A) $、$ q_i(1≦q_i≦B,q_i≦p_i) $ will be given divided by spaces.

Please output the remainder when the number of all the possible methods that can move all the flower in vase $ 1 $ to vase $ 2 $, modulo $ 1,000,000,007 $. Print a newline at the end of output.

### 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.