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

using namespace std;

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

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

/// functia care inmulteste doua matrice, fiecare de 2, pe 2 si pune rez in C

void Citire()
{
  fin >> n;
  P[0][0] = 0; P[0][1] = P[1][0] = P[1][1] = 1;
}

void Inmultire1()
{
    C[0][0] = X[0][0] * P[0][0] + X[0][1] * P[1][0];
    C[0][1] = X[0][0] * P[0][1] + X[0][1] * P[1][1];
    C[1][0] = X[1][0] * P[0][0] + X[1][1] * P[1][0];
    C[1][1] = X[1][0] * P[0][1] + X[1][1] * P[1][1];
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
           X[i][j] = C[i][j]%R;
}

void Inmultire2()
{
    C[0][0] = P[0][0] * P[0][0] + P[0][1] * P[1][0];
    C[0][1] = P[0][0] * P[0][1] + P[0][1] * P[1][1];
    C[1][0] = P[1][0] * P[0][0] + P[1][1] * P[1][0];
    C[1][1] = P[1][0] * P[0][1] + P[1][1] * P[1][1];
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
           P[i][j] = C[i][j]%R;
}

void Putere(int n)
{
     /// X-ul e I2
     X[0][0] = X[1][1] = 1;
     X[0][1] = X[1][0] = 0;
     while (n>0)
     {
        if (n & 1)
        {
            n--;
            Inmultire1();
        }
        n >>= 1;
        Inmultire2();
     }
    fout << X[1][1] << "\n";
}

int main ()
{
  Citire();
  if (n <= 1) fout << n << "\n";
  else          Putere(n-1);
  fin.close();
  fout.close();
  return 0;
}