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

#include <stdio.h>

#define MAXN		1024
#define MOD			4999999


int n;
int ans[MAXN];
int stdv[MAXN*MAXN];
int bk[MAXN][MAXN];

void prec()
{
	int i,i2;

	stdv[0] = 1;
	for(i=1;i<=n*n;i++)
		stdv[i] = (stdv[i-1]*2)%MOD;

	bk[1][0] = 1;
	bk[1][1] = 1;

	for(i=2;i<=n;i++)
	{
		bk[i][0] = 1;

		for(i2=1;i2<=i;i2++)
		{
			bk[i][i2] = (bk[i-1][i2-1] + bk[i-1][i2])%MOD;
		}
	}
}

int main()
{
	int i,i2;
	long long val;

	//freopen("zad2.out","w",stdout);

	scanf("%d",&n);

	prec();

	for(i=1;i<=n;i++)
	{
		ans[i] = 0;

		for(i2=1;i2<i;i2++)
		{
			val = ans[i2];
			val = (val*bk[i-1][i2-1])%MOD;
			val = (val*stdv[(i-i2)*(i-i2-1)/2])%MOD;

			ans[i] = (ans[i] + val)%MOD;
		}

		ans[i] = (stdv[i*(i-1)/2] - ans[i] + MOD)%MOD;
	}

	printf("%d\n",ans[n]);

	return 0;
}
