题目描述
我们称一个长度为
2n
2n 的数列是有趣的，当且仅当该数列满足以下三个条件：
它是从
1
1 到
2n
2n 共
2n
2n 个整数的一个排列
\{a_i\}
{ai
}；
所有的奇数项满足
a_1\lt a_3\lt \cdots \lt a_{2n-1}
a1
<⋯，所有的偶数项满足
a_2\lt a_4\lt \cdots \lt a_{2n}
a2
<⋯；
任意相邻的两项
a_{2i-1}
a2i−1
与
a_{2i}(1\le i\le n)
a2i
(1≤i≤n) 满足奇数项小于偶数项，即：
a_{2i-1}\lt a_{2i}
a2i−1
。
任务是：对于给定的
n
n，请求出有多少个不同的长度为
2n
2n 的有趣的数列。因为最后的答案可能很大，所以只要求输出答案
\bmod P
modP 的值。输入
只包含用空格隔开的两个整数
n
n 和
P
P。
输出
仅含一个整数，表示不同的长度为
2n
2n 的有趣的数列个数
\bmod P
modP 的值。
样例输入
3 10
样例输出
5
提示
样例说明
对应的 55 个有趣的数列分别为 {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\%
50% 的数据，
n\le 1000,P\le 10^6
n≤1000,P≤106；
对于全部数据，
1\le n\le 10^6,2\le P\le 10^9
1≤n≤106,2≤P≤109。
来源/分类
ybttg catalan数