Description

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

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

(2)所有的奇数项满足a1<a3<…<a2n-1，所有的偶数项满足a2<a4<…<a2n；

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

现在的任务是：对于给定的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）。

解题方法：

http://www.cnblogs.com/beiyuoi/p/5962846.html

http://www.cnblogs.com/hapjin/p/5758083.html

///BZOJ 1485 #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2000005;
LL P, ans=1;
int n, cnt;
bool check[maxn];
int minp[maxn], pr[maxn], c[maxn];

void predeal(int N)
{
    minp[1]=1;
    for(int i=2; i<= N; i++){
        if(!check[i]) pr[++cnt]=i, minp[i]=cnt;
        for(int j=1; j<=cnt && pr[j]*i<=N; j++){
            check[pr[j]*i]=1;
            minp[pr[j]*i]=j;
            if(i%pr[j]==0) break;
        }
    }
}

LL powmod(LL a, LL b){
    LL res=1;
    while(b){
        if(b&1) res=res*a%P;
        a=a*a%P;
        b>>=1;
    }
    return res;
}

void add(int x, int v){
    while(x>1){
        c[minp[x]]+=v;
        x/=pr[minp[x]];
    }
}

int main()
{
    scanf("%d%lld", &n,&P);
    predeal(2*n);
    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++) ans=ans*powmod(pr[i], c[i])%P;
    printf("%lld\n", ans);
    return 0;
}