#include <stdio.h>
#include <vector>

using uint = unsigned;
constexpr uint MASK = 1048576 - 1;

int main() {
  FILE *fin = fopen( "12perm.in", "r" );
  FILE *fout = fopen( "12perm.out", "w" );

  int n;
  fscanf( fin, "%d", &n );

  if( n <= 3 ){
    int fact[3 + 1] = { 1, 1, 2, 6 };
    fprintf( fout, "%d\n", fact[n] );
    fclose( fin );
    fclose( fout );
    return 0;
  }

  uint t1 = 2, t2 = 1, t3 = 1;
  uint st = 4;
  for( int i = 4; i <= n; i++ ){
    uint t0 = t1 + t3 + 1;
    st += t0;

    t3 = t2;
    t2 = t1;
    t1 = t0;
  }

  uint ret = 2 * (st - t2);
  fprintf( fout, "%d\n", int(ret & MASK) );

  fclose( fin );
  fclose( fout );
  return 0;
}