AT_abc281_g [ABC281G] Farthest City

题目描述

给定正整数 $N,\ M$。
请计算满足以下条件的 $N$ 个顶点的简单连通无向图（顶点编号为 $1,\dots,N$）的总数，并输出其对 $M$ 取余的结果。

• 对于所有 $u=2,\dots,N-1$，从顶点 $1$ 到顶点 $u$ 的最短距离严格小于从顶点 $1$ 到顶点 $N$ 的最短距离。

这里，从顶点 $u$ 到顶点 $v$ 的最短距离指的是连接顶点 $u$ 和 $v$ 的所有简单路径中所包含的边数的最小值。
另外，若存在某一对顶点 $u,v$，使得连接这两个顶点的边只存在于其中一个图中，则这两个图被认为是不同的。

输入格式

输入以以下格式从标准输入给出。

$N$ $M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 1000000000

输出 #1

8

输入输出样例 #2

输入 #2

3 100000000

输出 #2

1

输入输出样例 #3

输入 #3

500 987654321

输出 #3

610860515

说明/提示

限制条件

• $3 \leq N \leq 500$
• $10^8 \leq M \leq 10^9$
• $N,\ M$ 均为整数

样例解释 1

以下 $8$ 种情况满足条件。

样例解释 3

请注意要对 $M$ 取余。

由 ChatGPT 4.1 翻译