分数: 1600 点
问题陈述
你得到了一个偶数 N 和一个质数 M.
求模数 M,简单连通无向图 G 与 N 顶点编号 1 to N 满足以下条件:
- 对于每个生成树 T of G,有完美匹配 T.
什么是图表中的完美匹配?
对于图表 G,一组边 E 来自 G 称为完美匹配 G 如果,对于每个顶点 v 在图中, E 恰好包含一条边 v 作为端点。约束
- 2 \leq N \leq 500
- 10^8 \leq M \leq 10^9
- N 是偶数。
- M 是质数。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印答案。
示例输入 1
4 998244353
示例输出 1
15
例如,下图所示的两张图中,左边的图满足条件。另一方面,右图则不然,因为生成树中不存在完美匹配,三个边以粗体红色显示。

示例输入 2
10 998244353
示例输出 2
128792160
示例输入 3
300 923223991
示例输出 3
359143490