# include <fstream>
# include <iostream>
# define B 10000
using namespace std;
int n, v[100000], a[100000], s[1000000];

int main ()
{
	ifstream fin ("patrate2.in");
	ofstream fout ("patrate2.out");
	
	fin>>n;
	long long int q, t;
	int i, j;

	v[0]=v[1]=1;
	for(j=1;j<=n*n;++j)//2^n*n
	{
		for(i=1, t=0;i<=v[0] || t;++i, t/=B)
			v[i]=(t+=v[i]*2)%B;
		if (i-1>v[0])v[0]=i-1;
	}

	a[0]=a[1]=1;
	for(int k=2;k<=n;++k)//n!
	{
		for (i=1, t=0;i<=a[0] || t;++i, t/=B)
			a[i]=(t+=k*a[i])%B;
		if (i-1>a[0])a[0]=i-1;
	}

	for(int i=1;i<=v[0];++i)
	{
		for(t=0, j=1;j<=a[0] || t;++j, t/=B)
		{
			q=v[i]*a[j]+s[i+j-1];
			s[i+j-1]=(t+=q)%B;
		}
		if (i+j-2>s[0])s[0]=i+j-2;
	}
	for(int i=s[0];i;--i)
		fout<<s[i];
	return 0;
}