题目描述

有一个包含 $N$ 个带编号顶点的完全无向图。对于每一条边，你都需要给它赋予一个 $1$ 到 $K$ 之间的正整数边权。

请计算有多少种边权赋值方案，使得这个图的最小生成树唯一。

答案对质数 $M$ 取模。

两种方案不同，当且仅当至少有一条边的权值不同。

输入格式

输入一行三个整数：

N K M

输出格式

输出一个整数，表示满足最小生成树唯一的边权赋值方案数对 $M$ 取模后的结果。

数据范围

• $2\le N\le50$；
• $1\le K\le10^9$；
• $M$ 是质数；
• $\max(N,K)+1\le M\le10^9$。

样例 1

2 5 29

5

样例 2

3 3 11

4

当 $N=3$ 时，最小生成树唯一当且仅当三条边中的最大边权只出现一次。共有 $15$ 种合法赋值，$15\bmod11=4$。

样例 3

4 6 221772839

28380