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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, jie[130005], inv[130005], mii[130005], tmplen, rev[262205];
int len=1, A[262205], B[262205], C[262205], e[262205];
const int mod=1004535809, g=3;
int ksm(int a, int b){
int re=1;
while(b){
if(b&1) re = (ll)re * a % mod;
a = (ll)a * a % mod;
b >>= 1;
}
return re;
}
void ntt(int a[], int opt, int lim){
for(int i=0; i<lim; i++)
if(i<rev[i])
swap(a[i], a[rev[i]]);
for(int i=2; i<=lim; i<<=1){
int tmp=i>>1, wn;
if(opt==1) wn = ksm(g, (mod-1)/i);
else wn = ksm(ksm(g,mod-2), (mod-1)/i);
for(int j=0; j<lim; j+=i){
int w=1;
for(int k=0; k<tmp; k++){
int tmp1=a[j+k], tmp2=(ll)w*a[j+k+tmp]%mod;
a[j+k] = (tmp1 + tmp2) % mod;
a[j+k+tmp] = (tmp1 - tmp2 + mod) % mod;
w = (ll)w * wn % mod;
}
}
}
if(opt==-1){
int qwq=ksm(lim,mod-2);
for(int i=0; i<lim; i++)
a[i] = (ll)a[i] * qwq % mod;
}
}
void getNi(int d, int a[], int b[]){
if(d==1){
b[0] = ksm(a[0], mod-2);
return ;
}
getNi((d+1)>>1, a, b);
int lim=1, tmplim=0;
while(lim<=2*d) lim <<= 1, tmplim++;
for(int i=1; i<lim; i++)
rev[i] = (rev[i>>1]>>1) | ((i&1)<<(tmplim-1));
for(int i=0; i<d; i++)
e[i] = a[i];
for(int i=d; i<lim; i++)
e[i] = 0;
ntt(e, 1, lim);
ntt(b, 1, lim);
for(int i=0; i<lim; i++)
b[i] = (ll)(2-(ll)e[i]*b[i]%mod+mod)%mod*b[i]%mod;
ntt(b, -1, lim);
for(int i=d; i<lim; i++)
b[i] = 0;
}
int main(){
freopen("bzoj_3456.in", "r", stdin);
freopen("bzoj_3456.out", "w", stdout);
cin>>n;
jie[0] = jie[1] = inv[0] = inv[1] = mii[0] = mii[1] = 1;
for(int i=2; i<=n; i++){
inv[i] = (ll)(mod - mod / i) * inv[mod%i] % mod;
jie[i] = (ll)jie[i-1] * inv[i] % mod;
mii[i] = ksm(2, (ll)i*(i-1)/2 % (mod-1));
}
while(len<=2*n) len <<= 1, tmplen++;
for(int i=0; i<=n; i++)
B[i] = (ll)mii[i] * jie[i] % mod;
for(int i=1; i<=n; i++)
C[i] = (ll)mii[i] * jie[i-1] % mod;
getNi(n+1, B, A);
for(int i=0; i<len; i++)
rev[i] = (rev[i>>1]>>1) | ((i&1)<<(tmplen-1));
ntt(A, 1, len);
ntt(C, 1, len);
for(int i=0; i<len; i++)
A[i] = (ll)A[i] * C[i] % mod;
ntt(A, -1, len);
int ans=(ll)A[n]*ksm(jie[n-1],mod-2) % mod;
printf("%d\n", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
|