/*
TASK: str
LANG: C++
*/

#include<iostream>
using namespace std;

#define maxn 1010
#define mod 4999999

unsigned long long c[maxn][maxn],f[maxn],r[maxn];
unsigned long long i,j,k,n;


int main()
{
	cin>>n;
    f[2]=1;
	
    
    for(i=0;i<n;i++)
	{
		c[0][i]=1;
		c[i][i]=1;
	}
	for(i=2;i<n;i++)
		for(j=1;j<=i;j++)
			c[j][i]=(c[j][i-1]+c[j-1][i-1])%mod;
    
    
    for(j=2;j<n;j++)
        for(k=1;k<=j;k++)
			r[j]=(r[j]+c[k][j])%mod;	
	
    
    for(i=3;i<=n;i++)
	{
		f[i]=1;
		for(j=2;j<i;j++)			
			f[i]=(f[i]+(((f[j]*c[j][i-1])%mod)*r[j])%mod)%mod;
	}
    cout<<f[n]<<endl;  
	return 0;
}
