现在我们来描述一种带有参数 $N$ 的有向图，称为晾衣架图（Drying Rack Graph，简称 DRG）。

一个 DRG 包含 $N$ 个顶点组。第 $i$ 组 $V^i$ 包含 $2N$ 个顶点：$V^i_1, V^i_2, \dots, V^i_{2N}$。 DRG 中有两种类型的边：组内边（组内的边）和组间边（组与组之间的边）。

组内边 对于第 $i$ 组，存在以下组内边： $(V^i_j, V^i_{j+N})$，对于所有满足 $1 \le j \le N$ 的整数 $j$； $(V^i_j, V^i_{j+1})$，对于所有满足 $1 \le j \le N-1$ 或 $N+1 \le j \le 2N-1$ 的整数 $j$。

组间边 存在以下组间边： $(V^i_{i+N}, V^{i+1}_1)$，对于所有满足 $1 \le i \le N-1$ 的整数 $i$； $(V^1_i, V^i_{1+N})$，对于所有满足 $2 \le i \le N$ 的整数 $i$。

现在我们想知道参数为 $N$ 的 DRG 的拓扑序数量。 有向图 $G = (V, E)$ 的拓扑序是 $V(G)$ 中所有顶点的一个排列 $v_{p_1}, v_{p_2}, \dots, v_{p_{|V(G)|}}$，使得对于所有 $i < j$，$(v_{p_j}, v_{p_i}) \notin E(G)$。 为了避免计算巨大的整数，请报告答案对一个质数 $M$ 取模的结果。

输入格式

输入仅包含两个整数 $N, M$ ($1 \le N \le 5000, 2 * N * N < M \le 2^{30}$)，且 $M$ 是一个质数。

输出格式

输出一个整数，表示答案。

样例

样例输入 1

2 1073741789

样例输出 1

31

样例输入 2

3 1073741789

样例输出 2

7954100