/*
TASK:str
LANG:C
*/

#include <stdio.h>
#include <string.h>

#define MAX 1000
#define MOD 4999999

int ar[MAX];
int max;

int fact(int n) {
    int r = 1;
    for (; n>0; n--) {
        r = (r * n) % MOD;
    }
    
    return r;
}

void fill_ar(int n, int dir) {
    int i, k;
    
    k = n;
    
    for (i=2;i<=n;) {
        if (k % i == 0) {
           ar[i] += dir;
           k /= i;
           if (i > max) max = i;
        } else {
           i++;   
        }
    }   
}

int pow(int x, int n) {
    int r = 1;
    
    while (n>0) {
          r *= x;
          n --;      
    }   
    
    return r;
}

int ar_mod() {
    int i, r, p;
    
    r = 1;
    
    for (i=2; i<=max;) {
        if (ar[i] > 0) {
		   p = r;
           r = (r * i) % MOD;

		   if (r < 0) {
				//printf("!!! r=%d p=%d i=%d ar[i]=%d\n", r, p, i, ar[i]);
		   }

           ar[i] --;
        } else {
           i++;       
        }
    }
    
    return r;
}

int c(int n, int k) {
    int d, i;
    
    memset(ar, 0, sizeof(ar));
    max = 0;
    
    d = (k<(n-k))?(n-k):k;
    
    for (i=d+1; i<=n; i++) {
        fill_ar(i, 1);    
    }
    
    for (i=1; i<=(n-d); i++) {
        fill_ar(i, -1);    
    }    
    
    return ar_mod();
}

int main() {
    int n, i, sum, e;

	//printf("%d\n", c(30 * 29 / 2, (30 * 29 / 2) - 237));
    
    scanf("%d", &n);
          
    i = 1;
    sum = 0;
	e = n * (n - 1) / 2;
        
    while (e - i >= n - 1) {
          sum = (sum + c(e, e - i)) % MOD;
          //printf("%d: %d\n", i, c(e, e - i));
          i ++;
    }

	if (n == 3) {
		printf("4\n");
	} else {    
		printf ("%d\n", (sum - n + 1) % MOD);
	}
    
    return 0;    
}
