Busy Beaver 放弃了编程，决定转而从事现代艺术！

Busy Beaver 有两个带有颜料的标记。他想按照以下方式给一个无向图上色：

• 最初，所有顶点都是未上色的。首先，Busy Beaver 将一个标记放在顶点 1 上，另一个放在顶点 2 上。
• 然后，他沿着图的边滑动标记；每当一个顶点被标记覆盖时，该顶点就会被上色。（注意，顶点 1 和 2 在开始时即被上色。）
• 如果存在一种方式可以给所有顶点上色，且在整个过程中两个标记始终没有通过边直接相连，那么这个图被称为“艺术图”。

求 $N$ 个顶点上的艺术无向图的数量。由于答案可能很大，请输出其对质数 $P$ 取模的结果。

输入格式

每一组测试数据的唯一一行包含两个整数 $N$ 和 $P$ ($2 \le N \le 5000$; $5 \cdot 10^8 < P < 10^9$)。$P$ 是一个质数。

输出格式

输出 $N$ 个顶点上的艺术无向图的数量，对 $P$ 取模。

样例

输入格式 1

2 799999999

输出格式 1

1

输入格式 2

3 998244853

输出格式 2

2

输入格式 3

1984 998244853

输出格式 3

424428556

说明

在第一个测试用例中，只有两个顶点且没有边的图是唯一的艺术图。

在第二个测试用例中，下面前两个图是艺术图。最后一个图不是艺术图，因为它不可能给顶点 3 上色。