题目描述

给定整数 $N$ 和素数 $P$。

请计算满足以下条件的、编号为 $1$ 到 $N$ 的 $N$ 个顶点的连通无向图的个数，并输出其对 $P$ 取模的结果。

• 图 $G$ 中没有自环。允许存在重边。
• 对于 $G$ 的每一条边 $(u,v)$，即使将 $(u,v)$ 从 $G$ 中删除，$G$ 依然保持连通。也就是说，$G$ 是边双连通的。
• 对于 $G$ 的每一条边 $(u,v)$，如果将 $(u,v)$ 从 $G$ 中删除，$G$ 就不再是边双连通的。

当且仅当存在一对不同的顶点 $(u,v)$，使得两张图中连接 $u$ 和 $v$ 的边的数量不同，则认为这两张图不同。

输入格式

输入从标准输入中读取，格式如下：

$N$ $P$

输出格式

输出答案。

样例 1

输入

2 1005976817

输出

1

样例 2

输入

5 1000837403

输出

372

样例 3

输入

10 1001160547

输出

789846604

样例 4

输入

20 1006779551

输出

888612770

说明/提示

限制

• $2 \leq N \leq 50$
• $10^9 < P < 1.01 \times 10^9$
• $P$ 是素数。
• 所有输入值均为整数。

由 ChatGPT 4.1 翻译