题目描述

我们称一个长度为$\red{ 2n}$ 的数列是有趣的，当且仅当该数列满足以下三个条件：

1. 它是从$\red{ 1 }$到$\red{ 2n }$共$\red{ 2n }$个整数的一个排列$\red{ \{a_i\}}$；
2. 所有的奇数项满足 $\red{a_1\lt a_3\lt \cdots \lt a_{2n-1}​}$，所有的偶数项满足 $\red{a_2\lt a_4\lt \cdots \lt a_{2n}}$；
3. 任意相邻的两项$\red{ a_{2i-1}​ 与 a_{2i}(1\le i\le n)}$ 满足奇数项小于偶数项，即：$\red{a_{2i-1}\lt a_{2i}}$。

任务是：对于给定的 n，请求出有多少个不同的长度为$\red{ 2n }$的有趣的数列。因为最后的答案可能很大，所以只要求输出答案$\red{ \bmod P} 的值。

输入格式

只包含用空格隔开的两个整数$\red n$ 和$\red P$。

输出格式

仅含一个整数，表示不同的长度为$\red{ 2n }$的有趣的数列个数 $\red{\bmod P}$ 的值。

样例

输入样例

3 10

输出样例

5

对应的 $\red{5}$个有趣的数列分别为$\red{ \{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\}}$。

数据范围与提示

对于$\red{ 50\%}$ 的数据，$\red{n\le 1000}$,$\red{P\le 10^6}$； 对于全部数据，$\red{1\le n\le 10^6}$,$\red{2\le P\le 10^9}$。