该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P3200 [HNOI2009] 有趣的数列

题目描述

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

• 它是从 $1 \sim 2n$ 共 $2n$ 个整数的一个排列 $\{a_n\}_{n=1}^{2n}$；

• 所有的奇数项满足 $a_1<a_3< \dots < a_{2n-1}$，所有的偶数项满足 $a_2<a_4< \dots <a_{2n}$；

• 任意相邻的两项 $a_{2i-1}$ 与 $a_{2i}$ 满足：$a_{2i-1}<a_{2i}$。

对于给定的 $n$，请求出有多少个不同的长度为 $2n$ 的有趣的数列。
因为最后的答案可能很大，所以只要求输出答案对 $p$ 取模。

输入格式

一行两个正整数 $n,p$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

3 10

输出 #1

5

说明/提示

【数据范围】
对于 $50\%$ 的数据，$1\le n \le 1000$；
对于 $100\%$ 的数据，$1\le n \le 10^6$，$1\le p \le 10^9$。

【样例解释】
对应的 $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)$。