看到样例中n=3，答案=5，就有可能是卡特兰数。

做法：依次将1~2n内的每个数归入奇数项和偶数项，显然1要排在奇数项的第一位(整个序列的第一位)。

本题结论：奇数项数>=偶数项数

证明：
$\ \ \ $如果奇数项数 < 偶数项数，那么当将一个数归入奇数项时，因为是顺次枚举每个数，那么这个数将比上一个选出归入偶数项的数要大，即如果把这个数放入奇数项，肯定会比之后所有的偶数项都要大，显然会比相邻的偶数项要大，不满足条件，假设不成立。

#include <iostream>

using namespace std;

const int N = 2000010;

typedef long long LL;

int n , mod;
int primes[N] , cnt;
bool st[N];

int qmi(int a, int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (LL) res * a % mod;
        b >>= 1;
        a = (LL) a * a % mod;
    }
    return res;
}

void init(int n)
{
    for(int i = 2 ; i <= n ; i++)
    {
        if(!st[i]) primes[cnt++] = i;

        for(int j = 0 ; primes[j] <= n / i ; j++)
        {
            st[primes[j] * i] = true;

            if(i % primes[j] == 0) break;
        }
    }
}

int get(int x , int p)
{
    int s = 0;
    while(x) s += x / p , x /= p;
    return s;
}

int C(int a , int b)
{
    int res = 1;
    for(int i = 0 ; i < cnt ; i++)
    {
        int p = primes[i];
        int s = get(a , p) - get(b , p) - get(a - b , p);
        res = (LL) res * qmi(p , s) % mod;
    }
    return res;
}

int main()
{

    cin >> n >> mod;

    init(2 * n);//因为式子中会用到2*n

    cout << (C(2 * n , n) - C(2 * n , n - 1) + mod) % mod << endl;
    return 0;
}