题目描述

我们称一个长度为 \(2n\) 的数列是有趣的，当且仅当该数列满足以下三个条件：
1. 它是从 \(1\) 到 \(2n\) 共 \(2n\) 个整数的一个排列 \(\{a_i\}\)；
2. 所有的奇数项满足 \(a_1\lt a_3\lt \cdots \lt a_{2n-1}\)，所有的偶数项满足 \(a_2\lt a_4\lt \cdots \lt a_{2n}\)；
3. 任意相邻的两项 \(a_{2i-1}\) 与 \(a_{2i}(1\le i\le n)\) 满足奇数项小于偶数项，即：\(a_{2i-1}\lt a_{2i}\)。

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

输入格式

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

输出格式

仅含一个整数，表示不同的长度为 \(2n\) 的有趣的数列个数 \(\bmod 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,P\le 10^6\)；

对于全部数据，\(1\le n\le 10^6,2\le P\le 10^9\)。