102847: [AtCoder]ABC284 Ex - Count Unlabeled Graphs

Problem Statement

You are to generate a graph by the following procedure.

• Choose a simple undirected graph with $N$ unlabeled vertices.
• Write a positive integer at most $K$ in each vertex in the graph. Here, there must not be a positive integer at most $K$ that is not written in any vertex.

Find the number of possible graphs that can be obtained, modulo $P$. ($P$ is a prime.)

Two graphs are considered the same if and only if one can label the vertices in each graph as $v_1, v_2, \dots, v_N$ to satisfy the following conditions.

• For every $i$ such that $1 \leq i \leq N$, the numbers written in vertex $v_i$ in the two graphs are the same.
• For every $i$ and $j$ such that $1 \leq i \lt j \leq N$, there is an edge between $v_i$ and $v_j$ in one of the graphs if and only if there is an edge between $v_i$ and $v_j$ in the other graph.

Constraints

• $1 \leq K \leq N \leq 30$
• $10^8 \leq P \leq 10^9$
• $P$ is a prime.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$ $P$

Output

Print the answer.

Sample Input 1

3 1 998244353

Sample Output 1

4

The following four graphs satisfy the condition.

Sample Input 2

3 2 998244353

Sample Output 2

12

The following $12$ graphs satisfy the condition.

Sample Input 3

5 5 998244353

Sample Output 3

1024

Sample Input 4

30 15 202300013

Sample Output 4

62712469

问题描述

你需要通过以下步骤生成一个图。

• 选择一个具有$N$个无标签顶点的简单无向图。
• 在图中的每个顶点上写下不超过$K$的正整数。这里，不能有任何正整数不超过$K$而没有写在任何顶点上。

找出可以得到的可能图的数量，对$P$取模。（$P$是一个质数。）

只有当以下条件都满足时，才认为两个图是相同的。

• 对于每个$1 \leq i \leq N$，在两个图中顶点$v_i$上写下的数字是相同的。
• 对于每个$1 \leq i \lt j \leq N$，如果在一个图中存在边连接顶点$v_i$和$v_j$，则另一个图中也必须存在边连接顶点$v_i$和$v_j$，反之亦然。

约束条件

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

输入

输入通过标准输入给出，如下所示：

$N$ $K$ $P$

输出

打印答案。

样例输入1

3 1 998244353

样例输出1

4

以下四个图满足条件。

样例输入2

3 2 998244353

样例输出2

12

以下12个图满足条件。

样例输入3

5 5 998244353

样例输出3

1024

样例输入4

30 15 202300013

样例输出4

62712469