有趣的数列 卡特兰数

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

    (1)它是从1到2n共2n个整数的一个排列{a_i}；

    (2)所有的奇数项满足a₁<a₃<…<a_2n-1，所有的偶数项满足a₂<a₄<…<a_2n；

    (3)任意相邻的两项a_2i-1与a_2i(1≤i≤n)满足奇数项小于偶数项，即：a_2i-1<a_2i。

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

Input

输入文件只包含用空格隔开的两个整数n和P。输入数据保证，50%的数据满足n≤1000，100%的数据满足n≤1000000且P≤1000000000。

Output

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

Sample Input

3 10

Sample Output

5


对应的5个有趣的数列分别为（1,2,3,4,5,6），（1,2,3,5,4,6），（1,3,2,4,5,6），（1,3,2,5,4,6），（1,4,2,5,3,6）。

Hint

1.通项公式：h(n)=C(n,2n)/(n+1)=(2n)!/((n!)*(n+1)!) = C(n, 2n) - C(n +1, 2n)
2.递推公式：h(n)=((4*n-2)/(n+1))*h(n-1);
                      h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0).
3.前几项为：h(0)=1,h(1)=1,h(2)=2,h(3)=5,h(4)=14,

#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
#define pa pair<int,int>
#define mod 1000000007
#define inf 100000000
using namespace std;
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
ll ans=1;
int n,P,cnt;
int pri[1000005],mn[2000005],num[2000005];
bool del[2000005];
void getpri()
{
    for(int i=2;i<=2*n;i++)
    {
        if(!del[i])pri[++cnt]=i,mn[i]=cnt;
        for(int j=1;pri[j]*i<=2*n&&j<=cnt;j++)
        {
            del[pri[j]*i]=1;mn[pri[j]*i]=j;
            if(i%pri[j]==0)break;
        }
    }
}
void add(int x,int f)
{
    while(x!=1)
    {
        num[mn[x]]+=f;
        x/=pri[mn[x]];
    }
}
int main()
{
    n=read();P=read();
    getpri();
    for(int i=2*n;i>n;i--)add(i,1);
    for(int i=1;i<=n;i++)add(i,-1);
    add(n+1,-1);
    for(int i=1;i<=cnt;i++)
        while(num[i]--)ans=(ans*pri[i])%P;
    printf("%d
",ans);
    return 0;
}