← 返回题目列表

AtCoder · agc067_e

E. 双连通图

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

分数: 1900 点

问题陈述

给你一个整数 N 和素数 P.

计算数量,取模 P,无向连通图 G of N 顶点编号 1 to N 满足以下条件:

  • 中没有自循环 G。请注意,允许有多个边。
  • 对于所有边 (u,v) in G,如果我们删除 (u,v) 来自 G, G 保持连接。换句话说, G 是边双连通的。
  • 对于所有边 (u,v) in G,如果我们删除 (u,v) 来自 G, G 不再是边双连接的。

当且仅当存在一对不同的顶点时,两个图被认为是不同的 (u,v) 使得连接的边数 两个图中的 u 和 v 是不同的。

约束

  • 2 \le N \le 50
  • 10^9<P<1.01\times 10^9
  • P 是素数。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N P

输出

打印答案。


示例输入 1

2 1005976817

示例输出 1

1

示例输入 2

5 1000837403

示例输出 2

372

示例输入 3

10 1001160547

示例输出 3

789846604

示例输入 4

20 1006779551

示例输出 4

888612770