当前没有测试数据。

G - 最远的城市

得分 : $600$ 分

题目描述

给定正整数 $N$ 和 $M$。
找出满足以下条件的简单连通无向图的数量，对 $M$ 取模后的结果。

• 对于每个 $u = 2, \dots, N-1$，顶点 $1$ 到顶点 $u$ 的最短路径不严格小于顶点 $1$ 到顶点 $N$ 的最短路径。

这里，顶点 $u$ 到顶点 $v$ 的最短路径是连接顶点 $u$ 和 $v$ 的简单路径上的边的最小数量。
当且仅当两个图中存在顶点 $u$ 和 $v$，它们之间的边仅在其中一个图中，那么这两个图被认为不同。

约束条件

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

输入

从标准输入中以以下格式给出：

$N$ $M$

输出

输出答案。

4 1000000000

8

以下八个图满足条件。

3 100000000

1

500 987654321

610860515

求结果对 $M$ 取模。