#include<algorithm>
#define BAZ 1000000
#define DIM 5001
using namespace std;
long long n,b[DIM],sol[DIM],aux[DIM];
void inm2(long long x){
    long long i;
    long long t;
    for(i=1; i<=b[0]||t; t/=BAZ,++i)
        b[i]=(t+=b[i]*x)%BAZ;
    b[0]=i-1;}
void inm1(){
    long long i,j;
    long long t;
    memset(aux,0,sizeof(aux));
    for(i=1; i<=b[0]; ++i){
        for(j=1,t=0; j<=b[0]||t; t/=BAZ,++j)
			aux[i+j-1]=(t+=aux[i+j-1]+b[i]*b[j])%BAZ;
        if(i+j-2>aux[0])
            aux[0]=i+j-2;}
    memcpy(b,aux,sizeof(aux));}
void inm0(){
    long long i,j;
    long long t;
    memset(aux,0,sizeof(aux));
    for(i=1; i<=b[0]; ++i){
        for(j=1,t=0; j<=sol[0]||t; t/=BAZ,++j)
            aux[i+j-1]=(t+=aux[i+j-1]+b[i]*sol[j])%BAZ;
        if(i+j-2>aux[0])
            aux[0]=i+j-2;}
    memcpy(sol,aux,sizeof(aux));}
void fact(){
    long long i;
    memset(b,0,sizeof(b));
    for(i=2; i<=n; ++i)
        inm2(i);}
void pow(){
    long long p;
	for(p=n*n; p; p>>=1){
		if(p&1)
			inm0();
		inm1();}}
void solve(){
	long long i;
	scanf("%lld",&n);
	b[0]=sol[0]=sol[1]=1;
	b[1]=2;
	pow();
	fact();
	inm0();
	for(printf("%lld",sol[sol[0]]),i=sol[0]-1; i>0; --i){
		printf("%.6lld",sol[i]);}}
int main(){
    freopen("patrate2.in","r",stdin);
    freopen("patrate2.out","w",stdout);
    solve();
    return 0;}