好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

题目描述

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

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

任务是：对于给定的 $n$，请求出有多少个不同的长度为 $2n$ 的有趣的数列。因为最后的答案可能很大，所以只要求输出答案 $\bmod P$ 的值。

输入格式

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

输出格式

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

样例

样例输入

3 10

样例输出

5

样例解释

$n=3$，长度为 $6$，数字 $1$ 到 $6$。
满足条件的 $5$ 个有趣数列为：

1. $\{1,2,3,4,5,6\}$
2. $\{1,2,3,5,4,6\}$
3. $\{1,3,2,4,5,6\}$
4. $\{1,3,2,5,4,6\}$
5. $\{1,4,2,5,3,6\}$

这正好对应卡特兰数 $C_3 = 5$。

数据范围

• 对于 $50\%$ 的数据，$n \le 1000, P \le 10^6$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^6, 2 \le P \le 10^9$。

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

提示
该问题等价于求卡特兰数 $C_n = \frac{1}{n+1} \binom{2n}{n}$。
证明思路：将奇数位置和偶数位置看作两个栈，每次可以放一个数到奇数位置（等价于进左栈）或从奇数位置转移到偶数位置（出左栈进右栈），要求任何时候左栈大小不小于右栈，最终形成长度为 $2n$ 的序列。这是典型的卡特兰数模型。

因此答案为：

当 $P$ 不一定是质数时，需要将组合数的质因数分解出来，然后模 $P$ 计算。
注意 $n$ 最大 $10^6$，$\binom{2n}{n}$ 可用质因数分解 + 快速幂取模的方法计算。