#include<fstream.h>

int n,a[100000],c[100000],s[100000],b,x,i,t,j;

int main()

{

ifstream f("patrate2.in");
ofstream g("patrate2.out");

f>>n;  b=n*n;


s[0]=1; s[1]=1;
a[0]=1; a[1]=2;

while(b)

 {


   if(b%2)

    {  for(i=1; i<=a[0]; i++)

	 {

	    for(t=0,j=1;j<=s[0]||t;j++,t/=10)

	     c[i+j-1]=(t+=c[i+j-1]+a[i]*s[j])%10;

	      if(i+j-2>c[0]) c[0]=i+j-2;
	  }

       for(i=0;i<=c[0];i++)

	s[i]=c[i];

       for(i=1;i<=c[0];i++) c[i]=0; c[0]=0;
     }

   for(i=1; i<=a[0]; i++)

	 {

	    for(t=0,j=1;j<=a[0]||t;j++,t/=10)

	     c[i+j-1]=(t+=c[i+j-1]+a[i]*a[j])%10;

	      if(i+j-2>c[0]) c[0]=i+j-2;
	  }

       for(i=0;i<=c[0];i++)

	a[i]=c[i];

     for(i=1;i<=c[0];i++) c[i]=0; c[0]=0;

   b/=2;
 }

a[0]=1; a[1]=1;

 for(b=1;b<=n;b++)

  { t=0;

    for(i=1;i<=a[0]||t;i++,t/=10)

    a[i]=(t+=a[i]*b)%10;

    a[0]=i-1;
  }



for(i=1; i<=a[0]; i++)

  {

    for(t=0,j=1;j<=s[0]||t;j++,t/=10)

     c[i+j-1]=(t+=c[i+j-1]+a[i]*s[j])%10;

     if(i+j-2>c[0]) c[0]=i+j-2;
  }



for(i=c[0];i>0;i--) g<<c[i];

f.close();
g.close();

return 0;
}