1316

1316. 有趣的数列

题目

我们称一个长度为 $2n$ 的数列是有趣的，当且仅当该数列满足以下三个条件：

1. 它是从 $1$ 到 $2n$ 共 $2n$ 个整数的一个排列 $\lbrace a_i \rbrace$；
2. 所有的奇数项满足 $a_1<a_3< \cdots < a_{2n−1}$ ，所有的偶数项满足 $a_2<a_4< \cdots < a_{2n}$；
3. 任意相邻的两项 $a_{2i−1}$ 与 $a_{2i}$ $(1 \le i \le n)$ 满足奇数项小于偶数项，即：$a_{2i−1}<a_{2i}$。

任务是：对于给定的 $n$，请求出有多少个不同的长度为 $2n$ 的有趣的数列。

因为最后的答案可能很大，所以只要求输出答案 $\bmod P$ 的值。

输入格式

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

输出格式

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

数据范围

$1 \le n \le 10^6$,

$2 \le P \le 10^9$

输入样例：

3 10

输出样例：

5

样例解释

对应的 $5$ 个有趣的数列分别为 $\lbrace 1,2,3,4,5,6 \rbrace,\lbrace 1,2,3,5,4,6 \rbrace,\lbrace 1,3,2,4,5,6 \rbrace,\lbrace 1,3,2,5,4,6 \rbrace,\lbrace 1,4,2,5,3,6 \rbrace$。

题解