#include <iostream>

#define NMAX 1000000000
#define MOD 666013

using namespace std;

struct Matrix {
  long long a1, a2, a3, a4 ;
};

Matrix matbaz ;

Matrix inmultire (Matrix m1, Matrix m2 ) {
  Matrix mrez ;
  mrez.a1 = (m1.a1*m2.a1 + m1.a2 * m2.a3) % MOD ;
  mrez.a2 = (m1.a1*m2.a2 + m1.a2 * m2.a4) % MOD ;
  mrez.a3 = (m1.a3*m2.a1 + m1.a4 * m2.a3) % MOD ;
  mrez.a4 = (m1.a3*m2.a2 + m1.a4 * m2.a4) % MOD ;
  return mrez ;
}

int main()  {

  FILE *fin, *fout ;
  fin = fopen ("kfib.in", "r" ) ;
  fout = fopen ("kfib.out", "w" ) ;
  int n ;
  Matrix matrez ;
  fscanf (fin, "%d", &n ) ;
  matbaz.a1 = 0 ;
  matbaz.a2 = matbaz.a3 = matbaz.a4 = 1 ;
  matrez.a1 = matrez.a4 = 1 ;
  matrez.a3 = matrez.a2 = 0 ;
  n--;
  while (n > 0 ) {
    if (n % 2 == 0 ) {
      matbaz = inmultire (matbaz, matbaz ) ;
      n /= 2 ;
    }
    else {
      matrez = inmultire (matrez, matbaz ) ;
      n--;
    }
  }
  fprintf (fout, "%d", matrez.a4) ;
  return 0;
}