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

 int n;
 int a[1002];
 int bin[1000002];
 int fuck[1002];
 int comb[1002][1002];
 int g[1002];
 const int MOD=4999999;

 int main ()
  {
   int i,j,pom;
   scanf("%d",&n);
   fuck[0]=bin[0]=1;
   for (i=1;i<=n*n;i++)
    bin[i]=(bin[i-1]*2)%MOD;
   for (i=1;i<=n;i++)
    {
     fuck[i]=((long long)fuck[i-1]*(long long)i)%(long long)MOD;
     g[i]=bin[(i*(i-1))/2];
    }
   comb[0][0]=1;
   for (i=1;i<=n;i++)
    for (j=0;j<=i;j++)
     {
      comb[i][j]=comb[i-1][j];
      if (j!=0) comb[i][j]=(comb[i][j]+comb[i-1][j-1])%MOD;
     }
   a[1]=a[2]=1;
   for (i=3;i<=n;i++)
    {
     for (j=2;j<=i;j++)
      {
       pom=1;
       pom=((long long)pom*(long long)g[j-1])%(long long)MOD;
       pom=((long long)pom*(long long)a[i-j+1])%(long long)MOD;
       pom=((long long)pom*(long long)comb[i-1][i-j])%(long long)MOD;
       a[i]=(a[i]+pom)%MOD;
      }
     a[i]=(g[i]+MOD-a[i])%MOD;
    }
   printf("%d\n",a[n]);
   return 0;
  }
