题目描述

Antonio 最近对有机化学比较感兴趣，他想请你帮助他快速计算出某种烃类的同分异构体的数目。

为了表述方便，我们作出如下定义：

• 环烷烃： 具有 $n$ 个碳原子的环烷烃可以表示成一张具有 $n$ 个顶点 $n$ 条边的无向连通简单图(基环+外向树)。每个顶点的度数不超过 $4$。
• M-环烷烃：至多有 $m$ 个顶点在环上的环烷烃。（注意环上至少有 $3$ 个顶点，因为任意两个顶点之间至多只能有 $1$ 条边）。
• 同构：假设结构 $A$ 和结构 $B$ 均具有 $n$ 个碳原子，$A$ 和 $B$ 同构当且仅当能够对 $A$ 和 $B$ 中的每个碳原子都按照 $1~n$ 编号，使得对于编号为 $v_1$ 和 $v_2$ 的两个碳原子，他们在 $A$ 中存在边相连当且仅当他们在 $B$ 中存在边相连。（换言之，$A$ 和 $B$ 对应的图同构）。

现在，给出 $n$，$m$，Antonio 希望你帮助他统计有多少种互不同构的含有 $n$ 个碳原子的 M-环烷烃。由于这个数量可能很大，你只需要输出它对 $p$ 的余数。（$p$ 是一个素数）。

在本题中，我们不考虑某结构在化学上是否能够稳定存在，也不考虑其他的异构方式。

输入格式

输入文件只有一行，用空格隔开的三个整数 $n$，$m$，$p$ 。

输出格式

输出文件有且仅有一行，表示具有 $n$ 个碳原子的互不同构的M-环烷烃 的数量，对 $p$ 取模。

10 10 66103

475

提示

数据范围

$3 \le n \le 1000$，$3 \le m \le 50$，$m \le n$，$10^4 \le p \le 2 \times 10^9$，保证 $p$ 为素数。