#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;
  }

  std::vector<uint> tail({ 1, 1, 1, 2 });
  tail.reserve( n + 1 );
  for( int i = (int)tail.size(); i <= n; i++ )
    tail.push_back( tail[i - 1] + tail[i - 3] + 1 );

  uint ret = (n % 2) + tail[n];
  for( int poz_max = 1; 2 * poz_max + 1 < n; poz_max++ ){
    ret += tail[n - 2 * poz_max];
    ret += tail[n - 2 * poz_max - 1];
  }

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

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