题目描述

给定一个偶数 $N$ 和一个素数 $M$。

请你求出满足以下条件的 $N$ 个顶点、编号为 $1$ 到 $N$ 的简单连通无向图 $G$ 的个数，并对 $M$ 取模。

• 对于 $G$ 的任意一棵生成树 $T$，$T$ 上都存在一个完全匹配。

什么是图的完全匹配？对于图 $G$，完全匹配是指由 $G$ 的边组成的一个集合 $E$，使得对于图中每个顶点 $v$，恰好有一条以 $v$ 为端点的边属于 $E$。

输入格式

输入以以下格式从标准输入读入。

$N$ $M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 998244353

输出 #1

15

输入输出样例 #2

输入 #2

10 998244353

输出 #2

128792160

输入输出样例 #3

输入 #3

300 923223991

输出 #3

359143490

说明/提示

限制条件

• $2 \leq N \leq 500$
• $10^8 \leq M \leq 10^9$
• $N$ 是偶数
• $M$ 是素数
• 输入的所有值均为整数

样例说明 1

例如，下图中展示的两个图，左侧的图满足条件。而右侧的图，由于其红色粗线表示的包含 $3$ 条边的生成树上不存在完全匹配，因此不满足条件。

由 ChatGPT 4.1 翻译