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, i-th line consists of 3 integers: N_i (3 ≤ N_i, ΣN_i ≤ 10⁸ over all test cases),

K_i (1 ≤ K_i ≤ N_i - 2) and M_i (1 < M_i < 2⁶⁰), all pairs (N_i, K_i) are different.

Output

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.

Example

Input:
4 2 100
6 3 100
10000000 2 1000000007
10000000 5000000 1000000014000000049

Output:
2
21
984650007
780127215155143528