Description：

求合法数列的个数，数列满足以下三个条件：

$(1)$ 它是从 $1$ 到 $2n$ 共 $2n$ 个整数的一个排列

$(2)$ 所有的奇数项满足 $a_1<a_3<...<a_{2n-1}$ ，所有的偶数项满足 $a_2<a_4<...<a_{2n}$

$(3)$ 任意相邻的两项 $a_{2i-1}$ 与 $a_{2i}(1\le i\le n)$ 满足奇数项小于偶数项，即： $a_{2i-1}<a_{2i}$ 。

$1\le n\le 1000000$

Solution：

按顺序每次放要么放在第一个奇数项，要么放在第一个偶数项，这样一定能满足第一二个条件，由于第三个条件的限制，任意时刻奇数项小于偶数项，所以就是一个出栈序列，也就是说这题让我们求的是一个卡特兰数。模数不是质数分解质因子统计即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 2000010

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int mindiv[MAXN];

typedef long long ll;

int cnt[MAXN];

ll n,p;

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % p;

		a = a * a % p;

		b = b >> 1;

	}

	return res;

}

int main()

{

	for(int i = 2;i < MAXN;++i)isprime[i] = true;

	for(int i = 2;i < MAXN;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mindiv[i] = tot;

		}

		for(int j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

			mindiv[i * prime[j]] = j;

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

		}

	}

	cin >> n >> p;

	for(int i = 1;i <= 2 * n;++i)

	{

		int k = i;

		while(k != 1)

		{

			cnt[mindiv[k]]++;

			k /= prime[mindiv[k]];

		}

	}

	for(int i = 1;i <= n;++i)

	{

		int k = i;

		while(k != 1)

		{

			cnt[mindiv[k]] -= 2;

			k /= prime[mindiv[k]];

		}

	}

	int k = n + 1;

	while(k != 1)

	{

		cnt[mindiv[k]]--;

		k /= prime[mindiv[k]];

	}

	ll ans = 1;

	for(int i = 1;i <= tot;++i)ans = (ans * power(prime[i],cnt[i])) % p;

	cout << ans << endl;

	return 0;

}