该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

输入

4 1000000000

输出

8

样例 2

输入

3 100000000

输出

1

样例 3

输入

500 987654321

输出

610860515

说明/提示

限制条件

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

样例解释 1

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

样例解释 3

请注意要对 $M$ 取余。

由 ChatGPT 4.1 翻译