#include<iostream>
#include<fstream>
#define MOD 666013

using namespace std;

ifstream fin  ("kfib.in");
ofstream fout ("kfib.out");

int k;
long long int X[2][2], P[2][2], C[2][2];

void Inmultire1()
{
  C[0][0] = (X[0][0] * X[0][0])%MOD + (X[0][1] * X[1][0])%MOD;
  C[0][1] = (X[0][0] * X[0][1])%MOD + (X[0][1] * X[1][1])%MOD;
  C[1][0] = (X[1][0] * X[0][0])%MOD + (X[1][1] * X[1][0])%MOD;
  C[1][1] = (X[1][0] * X[0][1])%MOD + (X[1][1] * X[1][1])%MOD;

  X[0][0] = C[0][0] % MOD;
  X[0][1] = C[0][1] % MOD;
  X[1][0] = C[1][0] % MOD;
  X[1][1] = C[1][1] % MOD;
}

void Inmultire2()
{
  C[0][0] = (P[0][0] * X[0][0])%MOD + (P[0][1] * X[1][0])%MOD;
  C[0][1] = (P[0][0] * X[0][1])%MOD + (P[0][1] * X[1][1])%MOD;
  C[1][0] = (P[1][0] * X[0][0])%MOD + (P[1][1] * X[1][0])%MOD;
  C[1][1] = (P[1][0] * X[0][1])%MOD + (P[1][1] * X[1][1])%MOD;

  P[0][0] = C[0][0] % MOD;
  P[0][1] = C[0][1] % MOD;
  P[1][0] = C[1][0] % MOD;
  P[1][1] = C[1][1] % MOD;
}

void Putere(int k)
{
    P[0][0] = 1;
    P[0][1] = 0;
    P[1][0] = 0;
    P[1][1] = 1;

while (k>0)
{
   if (k%2 == 0)
   {
      k=k/2;
      Inmultire1(); /// x = x * x;
   }
   else
   {
      k--;
      Inmultire2(); /// p = p * x;
   }
}
}

int main ()
{
   fin >> k;
   X[0][0] = 0;
   X[0][1] = 1;
   X[1][0] = 1;
   X[1][1] = 1;

   Putere(k-1);
   fout << P[1][1] << "\n";
   fin.close();
   fout.close();
   return 0;
}