题目描述

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

找到满足以下条件的简单连通无向图的数量（对 $M$ 取模）：

• 对于每个 $u = 2, \\ldots, 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$

输出

输出答案。

示例输入 1

4 1000000000

示例输出 1

8

以下八个图满足条件。

示例输入 2

3 100000000

示例输出 2

1

示例输入 3

500 987654321

示例输出 3

610860515

请务必对 $M$ 取模。