#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)

#define repn(i,n) for(int i=1;i<=n;++i)

#define LL long long

#define pii pair <LL,LL>

#define fi first

#define se second

#define mpr make_pair

#define pb push_back

using namespace std;

const LL MOD=1004535809;

LL qpow(LL x,LL a)

{

	LL res=x,ret=1;

	while(a>0)

	{

		if((a&1)==1) ret=ret*res%MOD;

		a>>=1;

		res=res*res%MOD;

	}

	return ret;

}

namespace poly

{

  vector <LL> rev;

  void ntt(vector <LL> &a,LL G)

  {

    LL nn=a.size(),gn,g,x,y;vector <LL> tmp=a;

    rep(i,nn) a[i]=tmp[rev[i]];

    for(int len=1;len<nn;len<<=1)

    {

      gn=qpow(G,(MOD-1)/(len<<1));

      for(int i=0;i<nn;i+=(len<<1))

      {

        g=1;

        for(int j=i;j<i+len;++j,(g*=gn)%=MOD)

        {

          x=a[j];y=a[j+len]*g%MOD;

          a[j]=(x+y)%MOD;a[j+len]=(x-y+MOD)%MOD;

        }

      }

    }

  }

  vector <LL> convolution(vector <LL> a,vector <LL> b,LL G)

  {

    LL nn=1,bt=0,sv=a.size()+b.size()-1;while(nn<a.size()+b.size()-1) nn<<=1LL,++bt;

    while(a.size()<nn) a.pb(0);while(b.size()<nn) b.pb(0);

    rev.clear();

    rep(i,nn)

    {

      rev.pb(0);

      rev[i]=(rev[i>>1]>>1)|((i&1)<<(bt-1));

    }

    ntt(a,G);ntt(b,G);

    rep(i,nn) (a[i]*=b[i])%=MOD;

    ntt(a,qpow(G,MOD-2));

    while(a.size()>sv) a.pop_back();

    LL inv=qpow(nn,MOD-2);

    rep(i,a.size()) (a[i]*=inv)%=MOD;

    return a;

  }

  vector <LL> inverse(vector <LL> a,LL G)

  {

    if(a.size()==1) return vector <LL>{qpow(a[0],MOD-2)};

    vector <LL> aa=a;while(aa.size()>(a.size()+1)>>1) aa.pop_back();

    vector <LL> bb=inverse(aa,G);

    LL nn=1,bt=0,sv=a.size();while(nn<a.size()*2) nn<<=1LL,++bt;

    while(a.size()<nn) a.pb(0);while(bb.size()<nn) bb.pb(0);

    rev.clear();

    rep(i,nn)

    {

      rev.pb(0);

      rev[i]=(rev[i>>1]>>1)|((i&1)<<(bt-1));

    }

    ntt(a,G);ntt(bb,G);

    rep(i,nn) a[i]=(2LL-a[i]*bb[i]%MOD+MOD)*bb[i]%MOD;

    ntt(a,qpow(G,MOD-2));

    while(a.size()>sv) a.pop_back();

    LL inv=qpow(nn,MOD-2);

    rep(i,a.size()) (a[i]*=inv)%=MOD;

    return a;

  }

  vector <LL> sqrt1(vector <LL> a,LL G)//常数项为1

  {

    if(a.size()==1) return vector <LL>{1};

    vector <LL> aa=a;while(aa.size()>(a.size()+1)>>1) aa.pop_back();

    vector <LL> bb=sqrt1(aa,G);while(bb.size()<a.size()) bb.pb(0);

    vector <LL> bbb=inverse(bb,G);

    LL nn=1,bt=0,sv=a.size();while(nn<a.size()*2) nn<<=1LL,++bt;

    while(a.size()<nn) a.pb(0);while(bb.size()<nn) bb.pb(0);while(bbb.size()<nn) bbb.pb(0);

    rev.clear();

    rep(i,nn)

    {

      rev.pb(0);

      rev[i]=(rev[i>>1]>>1)|((i&1)<<(bt-1));

    }

    LL mul=qpow(2,MOD-2);

    ntt(a,G);ntt(bb,G);ntt(bbb,G);

    rep(i,nn) a[i]=mul*(bb[i]+bbb[i]*a[i]%MOD)%MOD;

    ntt(a,qpow(G,MOD-2));

    while(a.size()>sv) a.pop_back();

    LL inv=qpow(nn,MOD-2);

    rep(i,a.size()) (a[i]*=inv)%=MOD;

    return a;

  }

}

LL n,f[130010],fac[130010],inv[130010];

void solve(LL lb,LL ub)

{

  if(lb==ub)

  {

    if(lb==1) f[lb]=1;

    else f[lb]=(qpow(2,lb*(lb-1)/2LL)*inv[lb-1]%MOD-f[lb]+MOD)%MOD;

    return;

  }

  LL mid=(lb+ub)/2;

  solve(lb,mid);

  vector <LL> A,B,C;

  for(int i=lb;i<=mid;++i) A.pb(f[i]);

  rep(i,ub-lb+1) B.pb(qpow(2,(LL)i*(LL)(i-1)/2LL)*inv[i]%MOD);

  C=poly::convolution(A,B,3);

  for(int i=mid+1;i<=ub;++i) (f[i]+=C[i-lb])%=MOD;

  solve(mid+1,ub);

}

int main()

{

  fac[0]=1;repn(i,130005) fac[i]=fac[i-1]*(LL)i%MOD;

  rep(i,130004) inv[i]=qpow(fac[i],MOD-2);

  cin>>n;

  solve(1,n);

  cout<<f[n]*fac[n-1]%MOD<<endl;

	return 0;

}