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.
Subtask 1 [5%]
Subtask 2 [15%]
Subtask 3 [80%]
The input will be a single line containing two space-separated integers, and .
Output a single integer, the answer modulo .
Explanation for Sample
There are ways to get exactly intersection. The combinations are: and , and , and , and , and .