//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N=(1<<18)+5,mod=1004535809;int tmp[N],R[N],fac[N],A[N],B[N],C[N],niB[N];int pow(ll x,ll y){    ll res=1;    while(y){        if(y&1)res=res*x%mod;        x=x*x%mod,y>>=1;    }return (int)res;}void NTT(int *a,int n,int f){    int m=1,L=0;    for(;m<n;m<<=1)L++;    for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));    for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);    for(int l=1;l<n;l<<=1){        int wn=pow(3,((mod-1)/(l<<1)*f+mod-1)%(mod-1));        for(int j=0;j<n;j+=(l<<1)){            int w=1;            for(int k=0;k<l;k++,w=1ll*w*wn%mod){                int x=a[j+k],y=1ll*w*a[j+k+l]%mod;                a[j+k]=(x+y)%mod,a[j+k+l]=(x-y+mod)%mod;            }        }    }    if(f==-1){        int ni=pow(n,mod-2);        for(int i=0;i<n;i++)a[i]=1ll*a[i]*ni%mod;    }}void get_inv(int *a,int *b,int n){    if(n==1){b[0]=pow(a[0],mod-2);return;}    get_inv(a,b,n>>1);    memcpy(tmp,a,sizeof(int)*n);memset(tmp+n,0,sizeof(int)*n);    NTT(tmp,n<<1,1),NTT(b,n<<1,1);    for(int i=0;i<n<<1;i++)tmp[i]=((1ll*b[i]*(2-1ll*tmp[i]*b[i]%mod))%mod+mod)%mod;    NTT(tmp,n<<1,-1);    memcpy(b,tmp,sizeof(int)*n);memset(b+n,0,sizeof(int)*n);}signed main(){    int n,m,i;    scanf("%d",&n);for(m=1;m<=n;m<<=1);    for(fac[0]=1,i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;    for(i=0;i<=n;i++)B[i]=1ll*pow(2,(1ll*i*(i-1)/2)%(mod-1))*pow(fac[i],mod-2)%mod;    for(i=0;i<=n;i++)C[i]=1ll*pow(2,(1ll*i*(i-1)/2)%(mod-1))*pow(fac[i-1],mod-2)%mod;    get_inv(B,niB,m),NTT(niB,m,1);NTT(C,m,1);    for(int i=0;i<m;i++)A[i]=1ll*niB[i]*C[i]%mod;    NTT(A,m,-1);    printf("%lld\n",1ll*A[n]*fac[n-1]%mod);}