#include <cstring>
#include <iostream>
#include <fstream>
#define ONE 1
#define TWO 2
#define MAXL TWO
#define MOD 666013

using namespace std;

struct Matrice{
  int a[MAXL][MAXL];

  Matrice(int v[2][2]){
    memcpy(a, v, sizeof(a));
  }

  Matrice(){
    memset(a, 0, sizeof(a));
  }

  inline Matrice operator*(Matrice other){
    Matrice r = Matrice();
    for(int i = 0; i < MAXL; i ++){
      for (int j = 0; j < MAXL; j ++){
        long long sum = 0;
        for(int k = 0; k < MAXL; k ++){
          sum += (long long)a[i][k] * other.a[k][j];
          sum %= MOD;
        }
        r.a[i][j] = sum;
      }
    }

    return r;
  }
};

Matrice exprap(Matrice a, int pow){
  int identitate[2][2] = {{1, 0}, {0, 1}};
  Matrice r(identitate);
  while(pow > 0){
    if(pow % 2 == 1)
      r = a * r;
    a = a * a;
    pow /= 2;
  }

  return r;
}

int main(){
  int n;
  int fib0[2][2] = {{0, 1}, {0, 0}}; 
  int trecere[2][2] = {{1, 1}, {1, 0}}; 

  ifstream fin ("kfib.in");
  fin >> n;
  fin.close();

  ofstream fout ("kfib.out");
  Matrice r = Matrice(fib0) * exprap(Matrice(trecere), n);
  fout << r.a[0][0] << "\n";
  fout.close();

  return 0;
}