G - Gorgeous Vases Editorial /

Time Limit: 8 sec / Memory Limit: 256 MB

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

Input

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.

Output

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.

Input Example 1

3 1 0

Output Example 1

2

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.

Input Example 2

7 5 3
4 2
6 1
5 4

Output Example 2

0

Input Example 3

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

Output Example 3

763788532