最远的城市

题目描述

给你正整数 $N$ 和 $M$。

求满足以下条件的、顶点编号为 $1, \dots, N$ 的 $N$ 个顶点的简单连通无向图的个数,并对 $M$ 取模。

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

这里,从顶点 $u$ 到顶点 $v$ 的最短距离是连接顶点 $u$ 和 $v$ 的简单路径中边数的最小值。

两张图被认为是不同的,当且仅当存在两个顶点 $u$ 和 $v$,使得它们恰好在其中一张图中由一条边相连。

输入格式

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

$N$ $M$

输出格式

输出答案。

样例

4 1000000000

8

满足条件的图有下面 8 个。

3 100000000

1

500 987654321

610860515

一定要输出对 $M$ 取模后的结果。

数据范围

• $3 \le N \le 500$
• $10^8 \le M \le 10^9$
• $N$ 和 $M$ 是整数。