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.
Constraints
Subtask 1 [5%]

Subtask 2 [15%]

Subtask 3 [80%]

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
Copy
5 1
Sample Output
Copy
5
Explanation for Sample
There are
ways to get exactly
intersection. The combinations are:
and
,
and
,
and
,
and
,
and
.
Comments