#include<bits/stdc++.h>
using namespace std;
ifstream F("patrate2.in");
ofstream G("patrate2.out");
int n,j,i,t,a[6340],b[6340],c[6340],d[6340];
void A(int c[],int a[],int b[])
{
    int i,j,t;
    for(i=1;i<=a[0];++i) {
        for(t=0,j=1;j<=b[0]||t;c[i+j-1]=(t+=c[i+j-1]+a[i]*b[j])%10,++j,t/=10);
        if(i+j-2>c[0])
            c[0]=i+j-2;
    }
}
int main()
{
    for(F>>n,a[0]=a[1]=1,j=2;j<=n;a[0]=i-1,++j)
        for(t=0,i=1;i<=a[0]||t;a[i]=(t+=a[i]*j)%10,++i,t/=10);
    for(n*=n,b[0]=b[1]=c[0]=1,c[1]=2;n;memset(d,0,sizeof d),A(d,c,c),memcpy(c,d,sizeof d),n>>=1)
        if(n&1)
            memset(d,0,sizeof d),A(d,b,c),memcpy(b,d,sizeof d);
    for(memset(d,0,sizeof d),A(d,a,b),i=d[0];i;G<<d[i--]);
    return 0;
}