← 返回题目列表

AtCoder · abc284_h

Ex. 计算未标记的图形

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

您将通过以下过程生成图表。

  • 选择一个简单的无向图 N 未标记的顶点。
  • 最多写入一个正整数 图中每个顶点中的 K 。这里最多不能有正整数 K 未写入任何顶点。

找出可以获得的可能图的数量,取模 P. (P 是 素数.)

当且仅当可以将每个图中的顶点标记为 v_1, v_2, \dots, v_N 满足以下条件。

  • 对于每个 i 这样 1 \leq i \leq N,写入顶点的数字 两张图中的 v_i 是相同的。
  • 对于每个 i 和 j 这样 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

以下四张图满足条件。

image


示例输入 2

3 2 998244353

示例输出 2

12

以下 12 图表满足条件。

image2


示例输入 3

5 5 998244353

示例输出 3

1024

示例输入 4

30 15 202300013

示例输出 4

62712469