Problem Description

Input Format

Inputs will be given by standard input in the 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 separated 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 separated by spaces.

Output Format

Please output the remainder when the number of all the possible methods that can move all the flowers in vase $ 1 $ to vase $ 2 $, modulo $ 1,000,000,007 $.

Print a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 1 0

Sample Output #1

2

Sample Input #2

7 5 3
4 2
6 1
5 4

Sample Output #2

0

Sample Input #3

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

Sample Output #3

763788532

Notes/Hints

Problem

Cat Snuke has a pair of vases. One is noted as vase $ 1 $, the other one is noted as vase $ 2 $. Initially, vase $ 1 $ contains $ A $ blue flowers and $ B $ red flowers. Additionally, the number of blue flowers is larger than or equal to the number of red flowers, i.e., $ A ≧ B $. Vase $ 2 $ is empty, containing neither blue flowers nor red flowers.

Cat Snuke dislikes mixing a specific number of red flowers with a specific number of blue flowers. Such a combination is called 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 must follow the following rules:

• For vase $ 1 $ and vase $ 2 $, the number of 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 blue flowers and the number of red flowers must not be any Dirty Placement (at any time).

In accordance with the above rules, answer the number of all the possible methods that can move all the flowers 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 blue, blue, red, blue.
- The moving order is blue, red, blue, blue.

见题面 Input 部分

见题面 Output 部分