1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include<bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
if(res < 0) putchar('-'), res = -res;
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 1e6 + 5;
int n, mod;
int f[N << 1];
int fac[N], inv[N];
inline void init(int x)
{
fac[0] = inv[0] = inv[1] = 1;
for(int i = 1;i <= x;i ++) fac[i] = 1ll * fac[i - 1] * i % mod;
for(int i = 2;i <= x;i ++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
for(int i = 2;i <= x;i ++) inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
}
inline int C(int x, int y)
{
if(x < y || y < 0) return 0;
if(x <= mod && y <= mod) return 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;
return 1ll * C(x / mod, y / mod) * C(x % mod, y % mod) % mod;
}
inline int get_l(int x)
{
int l = 1;
while(l * 2 <= x) l <<= 1;
}
int sz[N << 1];
void dfs(int x)
{
if(x > n) return f[x] = 1, void();
dfs(x << 1), dfs(x << 1 | 1);
sz[x] += sz[x << 1] + sz[x << 1 | 1] + 1;
f[x] = 1ll * C(sz[x] - 1, sz[x << 1]) * f[x << 1] % mod * f[x << 1 | 1] % mod;
}
int main()
{
read(n, mod);
init(min(n, mod));
dfs(1);
write(f[1]);
return 0;
}
|