/*
LANG:C++
TASK:str
*/
#include <stdio.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define maxn 2048
#define mod 4999999

int n;
int C[maxn][maxn];
bool A[maxn][maxn];

int main() {
    scanf("%d",&n);
    int sn(n);
    n = (n*(n-1))/2 + 2;
    C[0][0] = 1;
    for(int i=1;i<n;i++) {
       for(int j=0;j<=i;j++) {
          if(j) {
                C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
          }
          else C[i][j] = C[i-1][j] % mod;
       }
    }
    #ifdef debC
    for(int i=0;i<n;i++) {
            for(int j=0;j<=i;j++)
                    printf("%d ",C[i][j]);
            printf("\n");
    }
    #endif
    long long ans = 0;
    ans = C[ (sn*(sn-1))/2 ][sn-2 ];
    ans %= mod;
    ans += C[ (sn*(sn-1))/2 ][ sn- 1 ];
    ans %= mod;
    int diag = 0;
    
    FOR(i,sn) FOR(j,sn) A[i][j] = 0;
    FOR(i,sn) {
       int c1,c2,c3;
       c3 = i + 1;
       c2 = i;
       c1 = i-1;
       if(c1<0) c1=sn-1;
       if(c3>=sn) c3 = 0;
       FOR(j,sn) {
          if(j!=c1 && j!=c2 && j!=c3) {
            if(!A[i][j]) {
                         A[i][j] = A[j][i] = 1;
                         diag++;
            }
          }
       }
    }
    if(sn<=3) {
      if(sn==1) { // no way ?
        printf("0\n");
      }
      else if(sn==2) {
        printf("2\n");
      }
      else if(sn==3) {
        printf("4\n");
      }
      return 0;
    }
    for(int i=1;i<=diag;i++) {
            ans += C[diag][i];
            ans %= mod;
    }
    printf("%d\n",ans);
    scanf("%d",&n);
    return 0;
}
