#include <fstream>
#include <iostream>
using namespace std;

const unsigned long long modulos=666013;

struct matrix
{
  unsigned long long a,b,
            c,d;
  matrix(unsigned long long a1,unsigned long long a2,unsigned long long a3,unsigned long long a4):a(a1),b(a2),c(a3),d(a4){}

};

ostream& operator << (ostream &out,matrix m)
{
  cout<<m.a<<" "<<m.b<<endl<<m.c<<" "<<m.d<<endl;
}


matrix operator * (matrix m1,matrix m2)
{
  matrix p((m1.a*m2.a+m1.b*m2.c)%modulos   ,   (m1.a*m2.b+m1.b*m2.d)%modulos,
                (m1.c*m2.a+m1.d*m2.c)%modulos   ,   (m1.c*m2.b+m1.d*m2.d)%modulos
                );
               /* matrix p((m1.a*m2.a+m1.b*m2.c)   ,   (m1.a*m2.b+m1.b*m2.d),
                (m1.c*m2.a+m1.d*m2.c)   ,   (m1.c*m2.b+m1.d*m2.d)
                );*/
  return p;
}


matrix pow_mat(int power,matrix start)
{
  if(power<=0)
    return matrix(1,1,1,1);
  if(power==1)
    return matrix(0,1,
                  1,1);
  if(power%2==0)
  {
    matrix m=pow_mat(power/2,start);
    return m*m;
  }
  matrix m=pow_mat(power/2,start);
  return m*m*start;
}

int main()
{
  int k;
  ifstream fin("kfib.in");
  fin>>k;

  matrix m=pow_mat(k-1,matrix(0,1,1,1));
  ofstream fout("kfib.out");
  fout<<m.d;


  return 0;
}