题目就是指定n，求卡特兰数Ca(n)%m。求卡特兰数有递推公式、通项公式和近似公式三种，因为要取余，所以近似公式直接无法使用，递推公式我简单试了一下，TLE。所以只能从通项公式入手。
Ca(n) = (2*n)! / n! / (n+1)!
思想就是把Ca(n)质因数分解，然后用快速幂取余算最后的答案。不过，算n!时如果从1到n依次质因数分解，肯定是要超时的，好在阶乘取余有规律，不断除素因子即可。
最后还是擦边过，可能筛法写得一般吧，也算是题目要求太柯刻。
/*
* Author : ben
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#ifdef ON_LOCAL_DEBUG
#else
#endif typedef long long LL;
const int MAXN = ;
const int N = ;
bool isPrime[N + ];//多用两个元素以免判断边界
int pn, pt[MAXN], num[MAXN]; void init_prime_table() {
memset(isPrime, true, sizeof(isPrime));
int p = , q, del;
double temp;
while (p <= N) {
while (!isPrime[p]) { p++; }
if (p > N) {//已经结束
break; }
temp = (double) p;
temp *= p;
if (temp > N)
break;
while (temp <= N) {
del = (int) temp; isPrime[del] = false;
temp *= p; }
q = p + ;
while (q < N) {
while (!isPrime[q]) { q++; }
if (q >= N) { break;}
temp = (double) p;
temp *= q;
if (temp > N) break;
while (temp <= N) {
del = (int) temp;
isPrime[del] = false;
temp *= p;
}
q++;
}
p++;
}
pn = ;
for (int i = ; i <= N; i++) {
if (isPrime[i]) {
pt[pn++] = i;
}
}
} int modular_exp(int a, int b, int c) {
LL res, temp;
res = % c, temp = a % c;
while (b) {
if (b & ) {
res = res * temp % c;
}
temp = temp * temp % c;
b >>= ;
}
return (int) res;
} void getNums(int n) {
int x = * n;
int len = pn;
for (int i = ; i < len && pt[i] <= x; i++) {
int r = , a = x;
while (a) {
r += a / pt[i];
a /= pt[i];
}
num[i] = r;
}
x = n;
for (int i = ; i < len && pt[i] <= x; i++) {
int r = , a = x;
while (a) {
r += a / pt[i];
a /= pt[i];
}
num[i] -= r;
}
x = n + ;
for (int i = ; i < len && pt[i] <= x; i++) {
int r = , a = x;
while (a) {
r += a / pt[i];
a /= pt[i];
}
num[i] -= r;
}
} int main() {
#ifdef ON_LOCAL_DEBUG
freopen("data.in", "r", stdin);
// freopen("test.in", "r", stdin);
// freopen("data.out", "w", stdout);
#endif
int n, m;
init_prime_table();
while (scanf("%d%d", &n, &m) == ) {
getNums(n);
LL ans = ;
int n2 = * n;
for (int i = ; ans && (i < pn) && pt[i] <= n2; i++) {
if (num[i] > ) {
ans = ans * (LL) modular_exp(pt[i], num[i], m);
ans %= m;
}
}
printf("%d\n", (int)ans);
}
return ;
}