[HNOI2009]有趣的数列

称一个长度为 $2n$ 的数列为“有趣的数列”，当且仅当它满足以下条件：

1. 该数列是整数 $1$ 到 $2n$ 的一个排列 $\{a_i\}$；
2. 所有奇数位置上的数严格递增，所有偶数位置上的数也严格递增，即： $$a_1<a_3<\cdots<a_{2n-1},\qquad a_2<a_4<\cdots<a_{2n};$$
3. 对于任意 $1\le i\le n$，相邻两项 $a_{2i-1}$ 与 $a_{2i}$ 满足： $$a_{2i-1}<a_{2i}.$$

给定 $n$，求不同的、长度为 $2n$ 的有趣数列共有多少个。由于答案可能很大，请输出答案对 $P$ 取模后的结果。

输入格式

输入一行，包含两个用空格分隔的整数 $n$ 和 $P$。

输出格式

输出一个整数，表示不同的、长度为 $2n$ 的有趣数列数量对 $P$ 取模后的结果。

样例输入

3 10

样例输出

5

样例解释

共有 $5$ 个符合要求的数列：

• $(1,2,3,4,5,6)$；
• $(1,2,3,5,4,6)$；
• $(1,3,2,4,5,6)$；
• $(1,3,2,5,4,6)$；
• $(1,4,2,5,3,6)$。

数据范围

• 对于 $50\%$ 的数据，$n\le 1000$；
• 对于 $100\%$ 的数据，$n\le 10^6$，$P\le 10^9$。

来源与许可

本题为 HNOI 2009 试题「有趣的数列」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 10

输出

5