#include <stdio.h>

using namespace std;

#define MOD 666013

struct Matrice {
  long long a11,a12,a21,a22;
};

Matrice matrez,matbaza;

Matrice inmultire(Matrice A,Matrice B){ ///inmultim mat a cu b
  Matrice rez;
  rez.a11=(A.a11*B.a11+A.a12*B.a21)%MOD;
  rez.a12=(A.a11*B.a12+A.a12*B.a22)%MOD;
  rez.a21=(A.a21*B.a11+A.a22*B.a21)%MOD;
  rez.a22=(A.a21*B.a12+A.a22*B.a22)%MOD;
  return rez;
}

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

  int n;
  fscanf(fin,"%d",&n);
  matbaza.a11=0;
  matbaza.a12=matbaza.a21=matbaza.a22=1; ///matbaza=matr constanta
  matrez.a11=matrez.a22=1; ///matrez=matr finala; initializam cu mat identitate (nu face nmc inm cu altcnv)
  matrez.a12=matrez.a21=0;
  n--;
  while(n>0){
    if(n%2==0){
      matbaza=inmultire(matbaza,matbaza);///^2, se injumatateste nr de inmultiri (matbaz^2)^n/2
      n/=2;
    }
    else{
      matrez=inmultire(matrez,matbaza); ///nu putem ridica la patrat ce avem, inmultim la rez final
      n--;
    }
  }
  fprintf(fout,"%d",matrez.a22); ///rasp final

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