#include <stdio.h>

#include <array>
using ll = long long;
constexpr int MOD = 666013;
struct Mat {
  std::array<std::array<int, 2>, 2> m;
  Mat operator * ( const Mat& that ) const {
    Mat ret;
    for( int i = 0; i < 2; i++ )
      for( int j = 0; j < 2; j++ )
        ret.m[i][j] = 0;

    for( int i = 0; i < 2; i++ )
      for( int j = 0; j < 2; j++ )
        for( int k = 0; k < 2; k++ )
          ret.m[i][j] = (ret.m[i][j] + m[i][k] * (ll)that.m[k][j]) % MOD;

    return ret;
  }
};

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

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

  Mat base = {
    {{
      { 0, 1 },
      { 1, 1 },
      }}
  }, ret = {
    {{
      { 1, 0 },
      { 0, 1 },
      }}
  };

  while( exp ){
    if( exp & 1 )
      ret = ret * base;
    base = base * base;
    exp >>= 1;
  }

  fprintf( fout, "%d\n", ret.m[0][1] );

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