#include<iostream>
#include<fstream>
#include<iomanip>

using namespace std;

int a[1005], b[1005], c[1005], p[1000], rez[10000];
ofstream g;

void afisare(int v[]){
    int i;
    g<<v[v[0]];
    for (i = v[0]-1; i >= 1; i--)
        g<<setw(4)<<setfill('0')<<v[i];
    g<<'\n';    
}

void produs(int a[], int b){
    int i;
    long long t = 0;
    for (i = 1; i <= a[0] || t; i++, t = t/10000)
        a[i] = ( t = t + a[i]*b)%10000;
    a[0] = i-1;
} 

void produsm(int a[], int b[], int c[]){
    int i, j, t = 0;
    for (i = 1; i <= b[0]; i++){
        t = 0;
        for ( j = 1; j <= a[0] || t; j++, t = t/10000 )
            c[i+j-1] = (t = t + a[j]*b[i] + c[i+j-1])%10000;
    }
    if (c[a[0]+b[0]] != 0)
        c[0] = a[0]+b[0];
    else c[0] = a[0]+b[0]-1;   
}

int main(){
    ifstream f("patrate2.in");
    g.open("patrate2.out");
    int n, nr, i, j, x;
    f>>n;
    
    c[0] = 1;
    c[1] = 1;
    for (i = 2; i <= n; i++){
        produs(c, i);
    }
    
    p[0] = 1;
    p[1] = 1;    
    n = n*n;
    while ( n >= 15){
        produs(p, 1<<15);
        n = n - 15;    
    }
    produs(p, 1<<n);
    
    produsm(p, c, rez);
    afisare(rez);
    
    return 0;
}