/*
TASK: str
LANG: C
*/
#include<stdio.h>

#define MAXN 1024
#define MOD 4999999
#define MIN(e1,e2) ((e1)<(e2)?(e1):(e2))

long long f[MAXN],sum[MAXN][MAXN],c[MAXN][MAXN],pow2[MAXN];

void init(int n)
{
	int i,j;
	c[0][0]=1; pow2[0]=1;
	for(i=1;i<=n;i++)
	{
		c[i][0]=1;
		for(j=1;j<=i;j++)
		{
			c[i][j]=c[i-1][j]+c[i-1][j-1];
			if(c[i][j]>=MOD) c[i][j]-=MOD;
		}
		pow2[i]=(2*pow2[i-1])%MOD;
	}
}

int calc(int n,int k)
{
	int i;
	long long res=0,cur=1;
	for(i=1;i*k<=n;i++)
	{
		cur*=(c[i*k-1][k-1]*(pow2[k]-1));
		cur%=MOD;
		cur*=f[k];
		cur%=MOD;
		res+=((cur*sum[n-i*k][MIN(n-i*k,k-1)])%MOD*c[n][n-i*k])%MOD;
		res%=MOD;
	}
	return res;
}

int main()
{
	int n,i,j;
	scanf("%d",&n);
	init(n);
	f[1]=1; sum[1][1]=1; sum[0][0]=1;
	for(i=2;i<=n;i++)
	{
		f[i]=sum[i-1][i-1];
		for(j=1;j<=i;j++)
		{
			sum[i][j]=sum[i][MIN(i,j-1)]+calc(i,j);
			sum[i][j]%=MOD;
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}
