← 返回题目列表

AtCoder · agc065_f

F. 永远完美

中文机器翻译题面 查看原题

分数: 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