/*
TASK: str
LANG: C
*/

#include <stdio.h>
#define MOD 4999999
#define MAXPAS 1000
#define MAXN 500100

int n;
long pas[MAXPAS][MAXPAS];
long a[2][MAXN];
long sum=0;

void makePas()
{ int i,j;

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

return;
}

void solve()
{ int i,br=3,j,k;

 scanf("%d", &n);
  if(n==1) { printf("1\n"); exit(0); }
  if(n==2) { printf("1\n"); exit(0); }
  if(n==3) { printf("4\n"); exit(0); }
  
  makePas();
  a[0][2]=3; a[0][3]=1;
  br=4; i=1;
    while(br<=n) {
        for(j=br/2; j<(br*(br-1)/2); j++)  {
          for(k=1; k<j; k++) {
            a[i][j]+=(a[!i][j-k]*pas[br-1][k])%MOD;
//            a[i][j]+=pas[i-1][k]/2;
            a[i][j]++;
         }
      }
    a[i][(br*(br-1))/2]=1;
    i=!i;
    br++;
   }

   i=!i;
   for(j=0; j<=(n*(n-1))/2; j++) sum+=a[i][j]%MOD;
   printf("%ld\n", sum);
return;
}

int main()
{
  solve();
 return 0;
}


