#include<iostream>
#include<fstream>
#define MOD 666013
using namespace std;
ifstream fin  ("kfib.in");
ofstream fout ("kfib.out");

long long int X[2][2], P[2][2];
long long int n;

void Initializare()
{
    P[0][0] = P[1][1] = 1;
    P[0][1] = P[1][0] = 0;
    X[0][0] = 0; X[1][1] = X[1][0] = X[0][1] = 1;
}

void Inmultire_1()
{
   long long int c1,c2,c3,c4;
   c1 = (X[0][0]*X[0][0])%MOD + (X[1][0]*X[0][1])%MOD;
   c2 = (X[0][0]*X[0][1])%MOD + (X[0][1]*X[1][1])%MOD;
   c3 = (X[1][0]*X[0][0])%MOD + (X[1][1]*X[1][0])%MOD;
   c4 = (X[1][0]*X[0][1])%MOD + (X[1][1]*X[1][1])%MOD;
   X[0][0] = c1 % MOD;
   X[0][1] = c2 % MOD;
   X[1][0] = c3 % MOD;
   X[1][1] = c4 % MOD;
}

void Inmultire_2()
{
   long long int c1,c2,c3,c4;
   c1 = (P[0][0]*X[0][0])%MOD  + (P[1][0]*X[0][1])%MOD;
   c2 = (P[0][0]*X[0][1])%MOD  + (P[0][1]*X[1][1])%MOD ;
   c3 = (P[1][0]*X[0][0])%MOD  + (P[1][1]*X[1][0])%MOD ;
   c4 = (P[1][0]*X[0][1])%MOD  + (P[1][1]*X[1][1])%MOD ;
   P[0][0] = c1 % MOD;
   P[0][1] = c2 % MOD;
   P[1][0] = c3 % MOD;
   P[1][1] = c4 % MOD;
}

void Ridicare_la_put()
{
  while (n>0)
  {
     if (n%2==0)
     {
        n=n/2;
        /// x=x*x;
        Inmultire_1();
     }
     /// p=p*x;
     Inmultire_2();
     n--;
  }
}


int main ()
{
  fin >> n; /// x
  Initializare();
  if (n==1) fout << "0\n";
  else if (n==2) fout << "1\n";
  else if (n==3) fout << "1\n";
  else
     Ridicare_la_put();
  fout << P[0][1] << "\n";
  fin.close();
  fout.close();
  return 0;
}