#include <bits/stdc++.h>
#define MAX 131072
#define MOD 1048576

using namespace std;

FILE *IN, *OUT;

int N;
int dp[5];

int pos, sign;
char f[MAX];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign = 1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

int main(){

    IN = fopen("12perm.in", "r");
    OUT = fopen("12perm.out", "w");

    Read(N);
    dp[1] = 1; dp[2] = 2; dp[3] = 6; dp[4] = 12;
    if(N <= 4)
        fprintf(OUT, "%d", dp[N]);
    for(int i = 5; i <= N; i++){
        int aux = dp[4];
        dp[4] = (dp[4] + dp[2] + 2 * (i - 2)) % MOD;
        dp[1] = dp[2];
        dp[2] = dp[3];
        dp[3] = aux;
    }
    fprintf(OUT, "%d", dp[4]);

    return 0;
}