首先看到2n，两个一组（a2i-1<a2i）可以想到卡特兰数
设奇数组的是（，偶数组的是），这就转化成了卡特兰数模型
这里用
C（2e6,1e6）大概有1e6位，但有mod p
一开始想*逆元（p不一定素数，exgcd）来搞定除数，但是逆元要求a和mod必须互质，显然不能满足所有数据，比如要乘4关于mod=100的逆元是无法求的
所以采用数分解质因数的方法，统计1~x每个质因数的幂，然后答案*=质因数^幂
这里计算从1~t质因数prime【i】总共的幂次
如1~10中3的幂数计算：10/3=3 ——有3个数3,6,9中有1个3
                                        3/3=1 ——其中9有2个3，上一个3已经被统计了，所以只要再加一次
#include<bits/stdc++.h>
using namespace std;
#define index iiii
typedef long long ll;
const int N=2e6+10;

ll n,mod,index,t,ans;
ll prime[N],cnt;
bool st[N];
ll qmi(ll a,ll b,ll mod){
	ll res=1;
	while(b){
		if(b&1) {
			res=res*a%mod;
		}
		a*=a, a%=mod;
		b>>=1;
	}
	return res;
}

void getPrime(ll n){
	for(int i=2;i<=n;i++){
		if(!st[i]) prime[cnt++]=i;
		for(int j=0;prime[j]<=n/i;j++){
			st[prime[j]*i]=true;
			if(i%prime[j]==0) break;
		}
	}
}
int main(){
	ans=1;
	cin>>n>>mod;
	getPrime(n<<1);
	for(int i=0;i<cnt;i++){
		index=0;
		t=n*2;
		while(t){
			t/=prime[i];
			index+=t;
		}
		t=n+1;
		while(t){
			t/=prime[i];
			index-=t;
		}
		t=n;
		while(t){
			t/=prime[i];
			index-=t;
		}
		ans=ans*qmi(prime[i],index,mod)%mod;

	}
	cout<<ans<<endl;
	return 0;
}