问题 4181 --10.有趣的数列

4181: 10.有趣的数列

题目描述

   我们称一个长度为 $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 的有趣的数列个数 mod P 的值。

样例输入输出

输入#1 复制
3 10
输出#1 复制
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≤106
对于全部数据,1≤n≤106,2≤P≤109

序号 标题 作者 发表时间 费用 订购数 操作