## DMOPC '17 Contest 5 P4 - Intersecting Arcs

View as PDF

Points: 17 (partial)
Time limit: 2.5s
Python 4.5s
Memory limit: 256M

Author:
Problem type

Bob has a row of dots and wants to connect certain pairs of them with an arc. Define to be an arc where and are the left and right endpoints respectively. Two arcs and have an intersection if exactly one of: or is true. There is an added constraint that no single dot may be the endpoint of two arcs. How many ways can the arcs be drawn so that there are exactly intersections following the given constraints? Since this number may be very large, please output it modulo . Two ways are different if there is an arc in one of them which is never drawn in the other. In particular, the order in which the arcs are drawn does not matter.

Python users are recommended to use PYPY over CPython. There is a significant performance increase.

#### Input Specification

The input will be a single line containing two space-separated integers, and .

#### Output Specification

Output a single integer, the answer modulo .

#### Sample Input

5 1

#### Sample Output

5

#### Explanation for Sample

There are ways to get exactly intersection. The combinations are: and , and , and , and , and .