SP13953 DTPOLY2 - Divide Polygon (HARD)

本题的简单版本：[DTPOLY](https://www.luogu.com.cn/problem/SP5649)。 我们现在来考虑一个包含 $N$ 个顶点的正多边形的切割方法。每一次，我们可以沿着某个多边形的一条弦（顶点与顶点的连线）进行切割，将这个多边形一分为二。假设每个顶点都是不同的。那么对于一个正方形（$4$ 个顶点的正多边形），我们一共有 $3$ 种方法切割它，沿两条对角线切割或者根本不切割。但是如果要将其切割成 $2$ 份则只有 $2$ 种方法；要将其切割成 $4$ 份是不可能的（注意每一次切割我们只对一个多边形操作，不能一次将 $2$ 个三角形切成 $4$ 个三角形）。 现在我们的问题就是，对于一个包含 $N$ 个顶点的正多边形，要把它切成 $K$ 份，有多少种切法？这个切法数目可能很多，只要求输出切法总数模 $M$ 的余数。你的任务就是编写程序解决这个问题。

**本题有多组测试数据。** 每组数据输入包含一行三个正整数表示 $N_i$、$K_i$ 和 $M_i$，所有 $(N_i,K_i)$ 互不相同，输入数据直到文件结束。

每组数据输出包含一行一个整数表示答案模 $M_i$ 的余数。

对于 $100\%$ 的数据，$3\le N_i,\sum N_i\le10^8,1\le K_i\le N_i-2,1