DTPOLY2  Divide Polygon (HARD)
This is hard version of 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
Input contains several test cases, ith line consists of 3 integers: N_{i} (4 ≤ N_{i}, ΣN_{i} ≤ 10^{8}), K_{i} (1 ≤ K_{i }≤ N_{i } 2) and M_{i} (1 < M < 2^{60}), all pairs (N_{i}, K_{i}) are different.
Output
On the ith line print the number of different ways to cut the polygon with N_{i} vertices into K_{i} pieces modulo M_{i}.
Example
Input: 4 2 100 6 3 100 10000000 2 1000000007 10000000 5000000 1000000014000000049
Output: 2 21 984650007 780127215155143528
hide comments
[Lakshman]:
20160601 10:36:46
Can some one help me. What complexity we need to get AC for the hard version. Mine O(N * log num) where (num) is the largest number to be factored.


[Rampage] Blue.Mary:
20140904 18:32:59
OK, finally got Accepted after changing my algorithm. BTW, the precision issues in this problem is so strange...


Francky:
20140904 18:32:59
Yeah!!! AC at first attempt, I could pass the 10(?) test files without too much optimizations, now is time for opti. The problem is very nice and I don't know problems here with a similar way to the green AC. Thanks a lot.


[Rampage] Blue.Mary:
20140904 18:32:59
1. You may create a new problem rather than simply change the problem description.


Francky:
20140904 18:32:59
@ Michael K.: You just have to accord the example with some moduli. <fixed>

Added by:  Michael Kharitonov 
Date:  20130301 
Time limit:  6s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 