#codefestival2015okinawag. [code_festival_2015_okinawa_g]Gorgeous Vases
[code_festival_2015_okinawa_g]Gorgeous Vases
Problem
Cat Snuke has a pair of vases. One is noted as vase , the other one is noted as vase . At first, the vase contains blue flowers and red flowers. In addition, the number of blue flowers is larger than or equal to the number of red flower, in other words, . In addition, vase 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 different Dirty Placements in total, the Dirty Placement is the combination of precisely blue flowers and red flowers.
Cat Snuke wants to move all the flowers that are in vase to vase one by one. However, Cat Snuke has to follow the following rules.
- For vase and vase , the number of the blue flowers should always be larger than or equal to that of the red flowers.
- For vase and vase , 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 to vase , modulo . Please note that all the flowers with the same color are indistinguishable (identical).
Input
Inputs will be given by standard input in following format
:
- For the first line, 、 will be given divided by spaces.
- From the second line there are additional lines to give all the Dirty Placements. For the line, integer 、 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 to vase , modulo .
Print a newline at the end of output.
Input Example 1
Output Example 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.