# BZOJ3456：城市規劃（EGF FFT/CDQ分治 FFT）

G(x)=∑i=1∞2(i2)xii!

G(x)=\sum_{i=1}^{\infty}2^{\binom{i}{2}}\frac{x^i}{i!}

F(x)=∑i=1nCnxii!

F(x)=\sum_{i=1}^{n}C_n\frac{x^i}{i!}

G(x)=∑i=0∞(F(x))ii!

G(x)=\sum_{i=0}^{\infty}\frac{(F(x))^i}{i!}

G(x)=eF(x)

G(x)=e^{F(x)}

F(x)=lnG(x)

F(x)=\ln G(x)

F′(x)=G′(x)G(x)

F'(x)=\frac{G'(x)}{G(x)}

#include<bits/stdc  .h>
using namespace std;
const int Mod=1004535809;
const int G=3,Maxn=5e5 50;
inline int power(int a,int b){
int rs=1;
for(;b;b>>=1,a=1ll*a*a%Mod)if(b&1)rs=1ll*rs*a%Mod;
return rs;
}
int tp[Maxn],tp2[Maxn];
struct FFT{
int pw[Maxn],pos[Maxn],k;
inline void dft(int *A,int len){
pw[0]=1;int tt=power(G,(Mod-1)/len);
for(int i=1;i<len;i  )pw[i]=1ll*pw[i-1]*tt%Mod;
for(int i=1;i<len;i  )pos[i]=(i&1)?((pos[i>>1]>>1)^(len>>1)):(pos[i>>1]>>1);
for(int i=1;i<len;i  )if(pos[i]>i)swap(A[pos[i]],A[i]);
for(int bl=1;bl<len;bl<<=1){
int tl=bl<<1,ct=len/tl,wn=pw[ct];
for(int p=0;p<len;p =tl){
int w=1;
for(int j=0;j<bl;j  ){
int &a=A[p j],&b=A[p j bl],t=1ll*b*w%Mod;
b=(a-t Mod)%Mod;
a=(a t)%Mod;
w=1ll*w*wn%Mod;
}
}
}
}
inline void calc_inv(int *A,int *B,int len){
if(len==1){
B[0]=power(A[0],Mod-2);
return;
}
if(len!=1)calc_inv(A,B,len>>1);
memcpy(tp,B,sizeof(int)*len);
memcpy(tp2,A,sizeof(int)*len);
int t=len<<1;
dft(tp,t);dft(tp2,t);
for(int i=0;i<t;i  ){
tp[i]=2ll*tp[i]%Mod-1ll*tp[i]*tp[i]%Mod*tp2[i]%Mod;
tp[i] =(tp[i]<0?Mod:0);
}
dft(tp,t);
int rv=power(t,Mod-2);
reverse(tp 1,tp t);
for(int i=0;i<len;i  ){
B[i]=1ll*tp[i]*rv%Mod;
}
}
}fft;
int n,A[Maxn],A_df[Maxn],inv_A[Maxn],fac[Maxn];
int main(){
scanf("%d",&n);
A[0]=A[1]=1;A_df[0]=1;
fac[0]=1;
for(int i=1;i<=n;i  )fac[i]=fac[i-1]*1ll*i%Mod;
for(int i=2;i<=n;i  ){
A[i]=1ll*power(2,(1ll*i*(i-1)/2)%(Mod-1))%Mod;
A[i]=1ll*A[i]*power(fac[i],Mod-2)%Mod;
A_df[i-1]=1ll*A[i]*i%Mod;
}
int t=1;while(t<n)t<<=1;
t<<=1;int tot=0;
fft.calc_inv(A,inv_A,t/2);
for(int i=0;i<n;i  ){
tot =1ll*A_df[i]*inv_A[n-i-1]%Mod;
tot-=(tot>Mod?Mod:0);
}
cout<<(1ll*tot*fac[n-1])%Mod<<endl;
}

#include<bits/stdc  .h>
using namespace std;
const int Mod=1004535809;
const int G=3;
const int N=5e5 50;
inline int power(int a,int b){
int rs=1;
for(;b;b>>=1,a=1ll*a*a%Mod)
if(b&1)rs=1ll*rs*a%Mod;
return rs;
}
struct fft{
int k,pos[N],w[N];
inline void pre(int len){
for(k=1;k<len;k<<=1);
k<<=1;w[0]=1;
int wn=power(G,(Mod-1)/k);
for(int i=1;i<k;i  )w[i]=1ll*w[i-1]*wn%Mod;
for(int i=1;i<k;i  )pos[i]=(pos[i>>1]>>1)|((i&1)?k>>1:0);
}
inline void dft(int *a){
for(int i=1;i<k;i  )if(i>pos[i])swap(a[i],a[pos[i]]);
for(int bl=1;bl<k;bl<<=1){
int tl=bl<<1,wn=w[k/tl];
for(int bg=0;bg<k;bg =tl){
int ws=1;
for(int j=0;j<bl;  j){
int &A=a[bg j],&B=a[bg j bl],t=1ll*B*ws%Mod;
B=(A-t Mod)%Mod;
A=(A t)%Mod;
ws=1ll*ws*wn%Mod;
}
}
}
}
inline void mul(int *a,int *b,int *c){
dft(a);dft(b);
for(int i=0;i<k;i  )c[i]=1ll*a[i]*b[i]%Mod;
dft(c);reverse(c 1,c k);
int rv=power(k,Mod-2);
for(int i=0;i<k;i  )c[i]=1ll*c[i]*rv%Mod;
}
}fft;
int n,pw[N],fac[N],inv_fac[N],a[N],b[N],f[N];
inline void solve(int l,int r){
if(l==r){f[l]=(pw[l]-1ll*f[l]*fac[l-1]%Mod Mod)%Mod;return;}
int mid=(l r)>>1;
solve(l,mid);
int len=r-l 1;fft.pre(len);
a[0]=0;b[0]=0;
for(int i=l;i<=mid;i  )a[i-l 1]=1ll*f[i]*inv_fac[i-1]%Mod;
for(int i=1;i<=len;i  )b[i]=1ll*pw[i]*inv_fac[i]%Mod;
for(int i=mid-l 2;i<=fft.k;i  )a[i]=0;
for(int i=len 1;i<=fft.k;i  )b[i]=0;
fft.mul(a,b,a);
for(int i=mid 1;i<=r;i  )f[i]=(f[i] a[i-l 1])%Mod;
solve(mid 1,r);
}
int main(){
scanf("%d",&n);
int len=1;
while(len<n)len<<=1;
len<<=1;pw[0]=1;fac[0]=(inv_fac[0]=1);
for(int i=1;i<=len;i  )pw[i]=power(2,(1ll*i*(i-1)/2)%(Mod-1));
for(int i=1;i<=len;i  )fac[i]=1ll*fac[i-1]*i%Mod;
for(int i=1;i<=len;i  )inv_fac[i]=power(fac[i],Mod-2);
solve(1,n);
cout<<f[n]<<endl;
}