#include<stdio.h>

#define INPUT "12perm.in"
#define OUTPUT "12perm.out"
#define MODULO 1048576

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long N;

void readValues()
{
  fscanf(fin, "%ld", &N);
}

void solveFunction()
{
  long A, B, C, poz, T;

  A = 1;
  B = 2;
  C = 6;
  poz = 3;

  for(long i = 3; i < N; ++i)
  {
    T = (C + A + 2 * ( poz - 1) + 1) % MODULO;
    A = B;
    B = C;
    C = T;
    ++poz;
  }

  fprintf(fout, "%ld\n", T);
}

int main()
{
  readValues();

  solveFunction();

  fclose(fin);
  fclose(fout);

  return 0;
}