#P17422. [PM13352] PatternLock

[PM13352] PatternLock

题目描述

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

一个解锁图案是一串点,并满足:

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

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

现在要求图案恰好包含全部 2N2N 个点。设合法图案总数为 XX,求 X mod MODX\bmod MOD。

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

输入格式

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

输出格式

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

数据范围

  • 1≤N≤35001\le N\le3500;
  • 2≤MOD≤109+72\le MOD\le10^9+7。

样例

1 12345667
2

样例说明

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