#include<fstream>  
using namespace std;  
#define MAXL (1<<10)
int nfact[MAXL];  
int lanp2[MAXL];  
int rezultat[(MAXL<<1)];  
void inmult(int fa){  
  int i,t;  
  for(i=1,t=0;i<=nfact[0]||t;i++,t/=10000)
    nfact[i]=(t+=nfact[i]*fa)%10000;
  nfact[0]=i-1;  
}  
void fact(int n){  
   int i;  
   nfact[0]=1;nfact[1]=1;  
   for(i=2;i<=n;i++)  
     inmult(i);  
}  
/*void inm(){
  int i, t;  
  for(i=1,t=0;i<=lanp2[0]||t;i++,t/=10)  
    lanp2[i]=(t+=(lanp2[i]<<1))%10;  
  lanp2[0]=i-1;  
}  
void ridic(int p){  
  int i;  
  lanp2[0]=1;lanp2[1]=2;  
  for(i=1;i<p;i++)  
    inm();  
} */
int sir[MAXL];
int C[MAXL];
void inmulteste(int A[], int B[]){
  int i, j, t;
  memset(C,0,sizeof(C));
  for(i=1;i<=A[0];i++){
    for(j=1,t=0;j<=B[0]||t;j++,t/=10000){
      C[i-1+j]=(t+=A[i]*B[j]+C[i-1+j])%10000;
    }  
  }  
  C[0]=i+j-3;
  memcpy(A,C,sizeof(C));
}
void ridic(int p){
  int i;
  lanp2[0]=1;lanp2[1]=2;
  sir[0]=1;sir[1]=2;
  p--;
  while(p){
     if((p&1)){
       inmulteste(lanp2,sir);
     }
     inmulteste(sir,sir);
     p>>=1;
  }
}
void inmultiremare(){  
  int i, j,t;  
  for(i=1;i<=nfact[0];i++){  
    for(j=1,t=0;j<=lanp2[0]||t;j++,t/=10000){
      rezultat[i-1+j]=(t+=nfact[i]*lanp2[j]+rezultat[i-1+j])%10000;
    }  
  }  
  rezultat[0]=i+j-3;  
}  
int main(){  
  int n;  
  ifstream f("patrate2.in");  
  f>>n;  
  f.close();  
  fact(n);  
  ridic(n*n);  
  inmultiremare();  
  ofstream g("patrate2.out");  
  int i;  
  for(i=rezultat[0];i>0;i--)  
    g<<rezultat[i];  
  g<<'\n';  
  g.close();  
  return 0;  
}