无标号图计数

题目描述

通过以下一系列操作生成一个图:

• 选择一个有 $N$ 个无标号顶点的简单无向图。
• 在图中每个顶点写入一个不超过 $K$ 的正整数。这里,不允许存在不超过 $K$ 的正整数没有被写在任何顶点上。

求通过上述操作能得到的可能的图的数量,对 $P$ 取模。($P$ 是素数。)

两个图被视为相同,当且仅当可以给两个图中的顶点分别标号 $v_1, v_2, \dots, v_N$,使得满足以下条件。

• 对于所有满足 $1 \le i \le N$ 的 $i$,两个图中顶点 $v_i$ 上写的数相同。
• 对于所有满足 $1 \le i \lt j \le N$ 的 $(i, j)$,两个图中 $v_i$ 与 $v_j$ 之间是否存在边一致。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$ $P$

输出格式

输出答案。

样例

3 1 998244353

4

满足条件的图有以下 $4$ 种。

3 2 998244353

12

满足条件的图有以下 $12$ 种。

5 5 998244353

1024

30 15 202300013

62712469

数据范围

• $1 \le K \le N \le 30$
• $10^8 \le P \le 10^9$
• $P$ 是素数。
• 输入中的所有值都是整数。