#include <fstream>

using namespace std;

ifstream fin( "kfib.in" );
ofstream fout( "kfib.out" );

const int MOD = 666013;

int N;
int init[2][2], mat[2][2], aux[2][2];

void Read()
{
  fin >> N;

  fin.close();
}

void Mat_pow( int power )
{
  if( power <= 1 ) return;

  Mat_pow( power / 2 );

  for( int i = 0; i < 2; ++i )
    for( int j = 0; j < 2; ++j )
    {
      aux[i][j] = 0;
      for( int I = 0, J = 0; J < 2; ++J, ++I )
      {
       aux[i][j] += ( 1LL * mat[i][J] * mat[I][j] ) % MOD;
       aux[i][j] %= MOD;
      }
    }

  for( int i = 0; i < 2; ++i )
    for( int j = 0; j < 2; ++j )
     mat[i][j] = aux[i][j];

  if( power % 2 )
  {
    for( int i = 0; i < 2; ++i )
     for( int j = 0; j < 2; ++j )
     {
       aux[i][j] = 0;
       for( int I = 0, J = 0; J < 2; ++J, ++I )
       {
        aux[i][j] += ( 1LL * mat[i][J] * init[I][j] ) % MOD;
        aux[i][j] %= MOD;
       }
     }
  }

  for( int i = 0; i < 2; ++i )
    for( int j = 0; j < 2; ++j )
     mat[i][j] = aux[i][j];
}

void Do()
{
  mat[0][0] = 0;
  mat[0][1] = mat[1][0] = mat[1][1] = 1;

  for( int i = 0; i < 2; ++i )
   for( int j = 0; j < 2; ++j )
    init[i][j] = mat[i][j];

  Mat_pow( N - 1 );

  /*for( int i = 0; i < 2; ++i )
  {
    for( int j = 0; j < 2; ++j )
      fout << mat[i][j] << ' ';

    fout << '\n';
  }*/

  fout << mat[1][1];
}

int main()
{
    Read();
    Do();

    return 0;
}