我们称一个长度为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的值。

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

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

3 10

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）。

 

/*

可以把形成序列的过程看成加数的过程，从小到大逐步加（这显然满足限制一），

然后加数的条件一是从小到大依次放奇数位或偶数位，因此也满足限制二，

然后无论何时偶数位上的数一定要大于等于奇数位上的数，这样也满足了限制三，

那么问题就转化成了按照如上条件放数的方案数，联系第二个条件，

也就是无论何时偶数位上的数一定要大于等于奇数位上的数，可以联想到栈，进栈次数一定要大于等于出栈次数，

不妨把放在偶数位上看成进栈，放在奇数位上看成出栈，这样就是求一个出栈的序列，也就是Catalan数列。

由于模数不一定是质数，可以分解质因数求。

*/

#include<bits/stdc++.h>

#define ll long long

#define N 2000007

using namespace std;

int n,mod,cnt;

ll pri[N],min_pri[N],num[N],ans=;

bool use[N];

void getpri()

{

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

    {

        if (!use[i]) pri[++cnt]=i,min_pri[i]=cnt;

        for (int j=; pri[j]*i<=*n&&j<=cnt; j++)

        {

            use[pri[j]*i]=,min_pri[pri[j]*i]=j;

            if (i%pri[j]==) break;

        }

    }

}

ll ksm(ll a,ll b)

{

    ll res=;

    while(b){

        if(b&) res=res*a%mod;

        b>>=;a=a*a%mod;

    }return res;

}

void add(int x,int opt)

{

    while (x!=)

    {

        num[min_pri[x]]+=opt;

        x/=pri[min_pri[x]];

    }

}

int main()

{

    scanf("%d%d",&n,&mod);

    getpri();

    for (int i=*n; i>n; i--) add(i,);

    for (int i=; i<=n+; i++) add(i,-);

    for (int i=; i<=cnt; i++) ans=ans*ksm(pri[i],num[i])%mod;

    printf("%lld\n",ans);

    return ;

}