AT_abc284_h [ABC284Ex] Count Unlabeled Graphs

题目描述

你需要通过以下一系列操作生成一个图。

• 自由选择一个没有顶点标签的 $N$ 个顶点的简单无向图。
• 给图的每个顶点各写上一个不超过 $K$ 的正整数。要求 $1$ 到 $K$ 的每个正整数都必须被写在某个顶点上，不能有遗漏。

请计算通过上述操作可能得到的不同图的数量，并对 $P$ 取模后输出（$P$ 是素数）。

注意，如果两个图可以分别给顶点加上标签 $v_1, v_2, \dots, v_N$，使得满足以下条件，则认为这两个图是相同的：

• 对于所有 $1 \leq i \leq N$，顶点 $v_i$ 上写的数在两个图中相同。
• 对于所有 $1 \leq i < j \leq N$，$v_i$ 和 $v_j$ 之间是否有边在两个图中相同。

输入格式

输入为一行，包含三个整数：

$N$ $K$ $P$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 1 998244353

输出 #1

4

输入输出样例 #2

输入 #2

3 2 998244353

输出 #2

12

输入输出样例 #3

输入 #3

5 5 998244353

输出 #3

1024

输入输出样例 #4

输入 #4

30 15 202300013

输出 #4

62712469

说明/提示

限制

• $1 \leq K \leq N \leq 30$
• $10^8 \leq P \leq 10^9$
• $P$ 是素数
• 输入的所有值均为整数

样例解释 1

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

样例解释 2

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

由 ChatGPT 4.1 翻译