该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_agc065_f [AGC065F] Always Perfect

题目描述

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

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

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

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

输入格式

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

$N$ $M$

输出格式

请输出答案。

样例 1

输入

4 998244353

输出

15

样例 2

输入

10 998244353

输出

128792160

样例 3

输入

300 923223991

输出

359143490

说明/提示

限制条件

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

样例说明 1

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

由 ChatGPT 4.1 翻译