卡特兰数。

这道题打下表可以看出前几项是卡特兰数（怎么想到打表和卡特兰数？我事先看了题解，为了确认一下。）

因为p不是质数，所以不能用乘法逆元。

我们可以把C(2*n,n)/(n+1)的每一项分解成一个质数，然后乘，这样就可以了。

#include
     
      #include
      
       #include
       
        #define LL long long using namespace std;const int maxn = 2000000 + 10;int prime[maxn],m[maxn],s[maxn];bool mark[maxn];int n,cnt,mod;LL res=1;void getpri() {    for(int i=2;i<=2*n;i++) {        if(!mark[i]) {prime[++cnt]=i; m[i]=cnt;}        for(int j=1;j<=cnt;j++) {            if(prime[j]*i>2*n) break;            mark[prime[j]*i]=1; m[prime[j]*i]=j;            if(i%prime[j]==0) break;        }    }}void add(int x,int f) {    while(x!=1) {        s[m[x]]+=f;        x/=prime[m[x]];    }}int main() {    scanf("%d%d",&n,&mod);    getpri();    for(int i=n+2;i<=2*n;i++) add(i,1);    for(int i=1;i<=n;i++) add(i,-1);    for(int i=1;i<=cnt;i++)         while(s[i]--) res=(res*prime[i])%mod;    printf("%lld\n",res);        return 0;    }