AT_agc065_f.[AGC065F] Always Perfect

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

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

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

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

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

$N$ $M$

请输出答案。

限制条件

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

样例说明 1

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

由 ChatGPT 4.1 翻译