题目链接： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3273

自从湖南旅游回来之后整个人真的是不佳啊~~~一天就做了这么一个题。。。感觉自己的越来越弱了。。。好了进入正题

分析：首先，这种题先找规律

当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，
则h(1)=1; 
当n=2时，1个根节点固定，还有n-1个节点，可以作为左子树，也可以作为右子树， 即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。这里h(0)表示空，所以只能算一种形态，即h(0)=1; 
当n=3时，1个根节点固定，还有n-1=2个节点，可以在左子树或右子树， 即：h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。 
以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种。
 
即符合Catalan数的定义，可直接利用通项公式得出结果。 递归式： 
  h(n)=h(n-1)*(4*n-2)/(n+1);  该递推关系的解为： 
  h(n)=C(2n,n)/(n+1) (n=1,2,3,...)

然后就啪啪啪、、、Wa了尼玛。。。作为弱者的我不知道怎么错了。。。后来看看递推里面带了除法。。。我去。。。我不会带除法的取余果断百度了一下。。。soga。。看了下要变乘法。。。ok直接套取余模版。。。然后就AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#define LL long long
using namespace std;
const int maxn=123456;
int n,m;
//LL ai[maxn];
int sm[1000],p;//将m分解质因数
int sa[1000];//4*i-2 和 i+1 分解质因数
//素数筛选
int flag[50000],pri[50000],pl;
void prime()
{
    for(int i=2; i<50000; i++)
    {
        if(flag[i]==0) pri[pl++]=i;
        for(int j=0; j<pl&&i*pri[j]<50000; j++)
        {
            flag[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
int extgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int r=extgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}
LL over;
void init()
{
    over=1%m;
    LL res=1;//n=1时 sum=1 后面从2开始
    p=0;
    int tm=m;//将m分解质因数
    for(int i=0; pri[i]*pri[i]<=tm; i++)
    {
        if(tm%pri[i]==0)
        {
            sm[p++]=pri[i];
            while(tm%pri[i]==0) tm/=pri[i];
        }
    }
    if(tm>1) sm[p++]=tm;//important
    memset(sa,0,sizeof(sa));
    for(int i=2; i<=n; i++)
    {
        int t;
        t=4*i-2;
        for(int j=0; j<p; j++)
        {
            while(t%sm[j]==0)
            {
                sa[j]++,t/=sm[j];
            }
        }
        res=res*t%m;
        t=i+1;
        for(int j=0; j<p; j++)
        {
            while(t%sm[j]==0)
            {
                sa[j]--,t/=sm[j];
            }
        }
        if(t>1)
        {
            int x,y;
            int r=extgcd(t,m,x,y);
            x=(x%m+m)%m;
            res=res*x%m;
        }
        LL tmp=res;
        for(int j=0; j<p; j++)
        {
            for(int k=0; k<sa[j]; k++)
            {
                tmp=tmp*sm[j]%m;
            }
        }
        over=(over+tmp)%m;
    }
}
void play()
{

    printf("%lld\n",over);
}
int main()
{
    prime();
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)break;
        init();
        play();
    }
    return 0;
}