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

int X[2][2], P[2][2];
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()
{
   int c1,c2,c3,c4;
   c1 = X[0][0]*X[0][0] + X[1][0]*X[0][1];
   c2 = X[0][0]*X[0][1] + X[0][1]*X[1][1];
   c3 = X[1][0]*X[0][0] + X[1][1]*X[1][0];
   c4 = X[1][0]*X[0][1] + X[1][1]*X[1][1];
   X[0][0] = c1 % MOD;
   X[0][1] = c2 % MOD;
   X[1][0] = c3 % MOD;
   X[1][1] = c4 % MOD;
}

void Inmultire_2()
{
   int c1,c2,c3,c4;
   c1 = P[0][0]*X[0][0] + P[1][0]*X[0][1];
   c2 = P[0][0]*X[0][1] + P[0][1]*X[1][1];
   c3 = P[1][0]*X[0][0] + P[1][1]*X[1][0];
   c4 = P[1][0]*X[0][1] + P[1][1]*X[1][1];
   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;
}