//minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define ll long long

 #define swap(x,y) (x^=y,y^=x,x^=y)

 #define mul(x,y) (1ll*(x)*(y)%P)

 #define add(x,y) (x+y>=P?x+y-P:x+y)

 #define dec(x,y) (x-y<0?x-y+P:x-y)

 using namespace std;

 const int N=,P=;

 inline int ksm(int a,ll b){

     int res=;

     while(b){

         if(b&) res=mul(res,a);

         a=mul(a,a),b>>=;

     }

     return res;

 }

 int n,r[N],A[N],B[N],fac[N],finv[N],O[N],C[N],F[N],G[N];

 inline void init(){

     fac[]=fac[]=finv[]=;

     for(int i=;i<=n;++i) fac[i]=mul(fac[i-],i);

     finv[n]=ksm(fac[n],P-);

     for(int i=n-;i;--i) finv[i]=mul(finv[i+],i+);

 }

 void NTT(int *A,int type,int len){

     int limit=,l=;

     while(limit<len) limit<<=,++l;

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

     r[i]=(r[i>>]>>)|((i&)<<(l-));

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

     if(i<r[i]) swap(A[i],A[r[i]]);

     for(int mid=;mid<limit;mid<<=){

         int R=mid<<,Wn=ksm(,(P-)/R);O[]=;

         for(int j=;j<mid;++j) O[j]=mul(O[j-],Wn);

         for(int j=;j<limit;j+=R){

             for(int k=;k<mid;++k){

                 int x=A[j+k],y=mul(O[k],A[j+k+mid]);

                 A[j+k]=add(x,y),A[j+k+mid]=dec(x,y);

             }

         }

     }

     if(type==-){

         reverse(A+,A+limit);

         for(int i=,inv=ksm(limit,P-);i<limit;++i)

         A[i]=mul(A[i],inv);

     }

 }

 void Inv(int *a,int *b,int len){

     if(len==) return (void)(b[]=ksm(a[],P-));

     Inv(a,b,len>>);

     for(int i=;i<len;++i) F[i]=a[i],G[i]=b[i];

     NTT(F,,len<<),NTT(G,,len<<);

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

     F[i]=mul(mul(F[i],G[i]),G[i]);

     NTT(F,-,len<<);

     for(int i=;i<len;++i) b[i]=(1ll*(b[i]<<)%P+P-F[i])%P;

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     scanf("%d",&n);init();

     int len=;for(len=;len<=(n*);len<<=);

     A[]=;

     for(int i=;i<=n;++i) A[i]=mul(ksm(,1ll*i*(i-)/),finv[i]);

     Inv(A,B,len);

     for(int i=;i<=n;++i) C[i]=mul(ksm(,1ll*i*(i-)/),finv[i-]);

     NTT(B,,len),NTT(C,,len);

     for(int i=;i<len;++i) B[i]=mul(B[i],C[i]);

     NTT(B,-,len);

     printf("%d\n",mul(B[n],fac[n-]));

     return ;

 }