题目描述

我们称一个长度为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 \leq i \leq n)$满足奇数项小于偶数项，

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

输入描述

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

输出描述

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

示例1

输入

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 \leq 1000,P \leq 10^6$； 对于全部数据，$1 \leq n \leq 10^6,2 \leq P \leq 10^9$。