题目描述

屏幕上有一个 $2\times N$ 的点阵。两行点的坐标分别为 $(0,0),(0,1),\ldots,(0,N-1)$ 与 $(1,0),(1,1),\ldots,(1,N-1)$。

一个解锁图案是一串点，并满足：

• 每个点最多出现一次；
• 对于图案中任意两个相邻点 $A,B$，如果线段 $AB$ 上还存在其他点阵中的点，那么这些点必须在 $A,B$ 之前就已经出现在图案中。

例如，$(0,1)\to(0,0)\to(0,2)$ 是合法的，因为连接 $(0,0)$ 与 $(0,2)$ 时，中间的 $(0,1)$ 已经访问过；而图案不能以 $(0,0)\to(0,2)$ 开始。

现在要求图案恰好包含全部 $2N$ 个点。设合法图案总数为 $X$，求 $X\bmod MOD$。

两个图案只有在点的访问顺序完全相同时才视为相同。

输入格式

一行输入两个整数 $N,MOD$。

输出格式

输出一个整数，表示合法图案数量对 $MOD$ 取模后的结果。

数据范围

• $1\le N\le3500$；
• $2\le MOD\le10^9+7$。

样例

1 12345667

2

样例说明

只有两种合法图案：$(0,0)\to(1,0)$ 与 $(1,0)\to(0,0)$。