题目描述

我们称一个长度为 $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≤1000,P≤10^6$ ；

对于全部数据，$1≤n≤10^6 ,2≤P≤10^9$ 。

来源

一本通在线评测