SP13953 DTPOLY2 - Divide Polygon (HARD)

This is hard version of [DTPOLY](../DTPOLY/). Determine the number of ways to cut a convex polygon with **N** vertices if the only cuts allowed are from vertex to vertex, each cut divides exactly one polygon into exactly two polygons, and you must end up with exactly **K** polygons. Consider each vertex distinct. For example, there are three ways to cut a square - the two diagonals and not cutting at all - but only two ways to cut it to form 2 polygons, and only one way to cut it to form 1 polygon. The order of cuts does not matter. Since the number of ways can be very large, you should return the number taken modulo **M**.

Input contains several test cases, i-th line consists of 3 integers: **N $ _{i} $** (3 N $ _{i} $ , **Σ****N $ _{i} $** **K $ _{i} $** (1 K $ _{i } $ N $ _{i } $ - 2) and **M $ _{i} $** (1 < **M $ _{i} $** < 2 $ ^{60} $ ), all pairs (**N $ _{i} $** , **K $ _{i} $** ) are different.

On the i-th line print the number of different ways to cut the polygon with **N $ _{i} $** vertices into **K $ _{i} $** pieces modulo **M $ _{i} $** .