#include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Mod 1004535809

 #define LL long long

 #define Maxn 130000*4

 const int G=;

 int fac[Maxn],F[Maxn],H[Maxn],V[Maxn];

 int qpow(int x,int b)

 {

     int ans=;

     while(b)

     {

         if(b&) ans=1LL*ans*x%Mod;

         x=1LL*x*x%Mod;

         b>>=;

     }

     return ans;

 }

 int R[Maxn];

 void NTT(int *a,int nn,int t)

 {

     for(int i=,j=;i<nn;i++)

     {

         if(i>j)    swap(a[i],a[j]);

         for(int l=(nn>>);(j^=l)<l;l>>=);

     }

     for(int i=;i<nn;i<<=)

     {

         int wn=qpow(G,(Mod-)/(i<<));

         for(int j=;j<nn;j+=(i<<))

         {

             int w=;

             for(int k=;k<i;k++)

             {

                 int x=a[j+k],y=1LL*w*a[j+k+i]%Mod;

                 a[j+k]=(x+y)%Mod;a[j+k+i]=((x-y)%Mod+Mod)%Mod;

                 w=1LL*w*wn%Mod;

             }

         }

     }

     if(t==-)

     {

         int inv=qpow(nn,Mod-);

         reverse(a+,a+nn);

         for(int i=;i<=nn;i++) a[i]=1LL*a[i]*inv%Mod;

     }

 }

 // int temp[Maxn];

 void get_inv(int *a,int *b,int len)

 {

     static int temp[Maxn];

     if(len==)

     {

         b[]=qpow(a[],Mod-);

         b[]=;

         return;

     }

     get_inv(a,b,len>>);

     for(int i=;i<=len;i++) temp[i]=a[i];

     for(int i=len+;i<=len<<;i++) temp[i]=;

     // memcpy(temp,a,sizeof(int)*len);

     // memset(temp+len,0,sizeof(int)*len);

     NTT(temp,len<<,),NTT(b,len<<,);

     for(int i=;i<(len<<);i++) b[i]=1LL*b[i]*(-1LL*temp[i]*b[i]%Mod+Mod)%Mod;

     NTT(b,len<<,-);

     memset(b+len,,sizeof(int)*len);

 }

 int n,m;

 void fal()

 {

     for(int i=;i<=m;i++) H[i-]=1LL*F[i]*i%Mod;

     get_inv(F,V,m);

     NTT(H,m,);NTT(V,m,);

     for(int i=;i<=m;i++) F[i]=1LL*H[i]*V[i]%Mod;

     NTT(F,m,-);

     for(int i=n;i>=;i--) F[i]=1LL*F[i-]*qpow(i,Mod-)%Mod;

 }

 int main()

 {

     scanf("%d",&n);

     m=;while(m<=*n) m<<=;

     fac[]=;for(int i=;i<=n;i++) fac[i]=1LL*fac[i-]*i%Mod;

     F[]=;

     for(int i=;i<=n;i++)

     {

         F[i]=1LL*qpow(,1LL*i*(i-)/%(Mod-))*qpow(fac[i],Mod-)%Mod;

     }

     fal();

     F[n]=1LL*F[n]*fac[n]%Mod;

     printf("%d\n",F[n]);

     return ;

 }