#include <stdio.h>

#define FIN "12perm.in"
#define FOUT "12perm.out"
#define MOD 1048576

int N, A[4];

int main(void)
{
    int i, t;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &N);

    A[0] = 2; A[1] = 6; A[2] = 12;
    for (i = 3; i < N; i++)
         A[i&3] = (A[(i+3)&3] + A[(i+1)&3] + (i<<1)) % MOD;

    printf("%d\n", A[(N-2)&3]);

    return 0;
}