#include <iostream>
#include <fstream>

#define For(i, x, y) for(int i = x; i <= y; ++i)
#define Forr(i, x, y) for(int i = x; i >= y; --i)
#define mod 666013
#define S(x, y) ((x + y) % mod)
#define P(x, y) ((1LL*x * y) % mod)
using namespace std;

int k, sol[3][3], mat[3][3], aux[3][3];
void mems(int A[][3]){
  For(i, 0, 1)
    For(j, 0, 1)
      A[i][j] = 0;
}
void memc(int A[][3], int B[][3]){
  For(i, 0, 1)
    For(j, 0, 1)
      A[i][j] = B[i][j];
}
void mult(int A[][3], int B[][3], int C[][3]){
   For(i, 0, 1)
     For(j, 0, 1)
      For(k, 0, 1)
        C[i][j] = S(C[i][j], P(A[i][k], B[k][j]));
}
void lg_power(long long p){
  mems(sol);
  sol[0][0] = sol[1][1] = 1;
  while(p){
    if(p % 2 == 0){
      mems(aux);
      mult(mat, mat, aux);
      memc(mat, aux);
      p /= 2;
    }
     else {
        mems(aux);
        mult(sol, mat, aux);
        memc(sol, aux);
        p--;
     }
  }
}
int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    mat[0][0] = 0;
    mat[0][1] = mat[1][0] = mat[1][1] = 1;
    fin >> k;
    if(k == 0) {
        fout << 0;
        return 0;
    }
    lg_power(k - 1);
    fout << sol[1][1];
    return 0;
}