#include<algorithm>
#define BAZ 1000000000
#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,t=0; 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,b[0]=b[1]=1; 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("%.9lld",sol[i]);}}
int main(){
	freopen("patrate2.in","r",stdin);
	freopen("patrate2.out","w",stdout);
	solve();
	return 0;}