#include<stdio.h>
#include<assert.h>

#include<vector>
#include<algorithm>

using namespace std;

const int kmod = 666013;

class matrix{
public:
  int lines, cols;
  int **p;

  matrix(){};

  matrix(int x, int y){
    lines = x;
    cols = y;
    p = new int *[lines];

    for(int i = 0; i < lines; ++i)
      p[i] = new int [cols];
  };

  int elem(int x, int y){
    return p[x][y];
  }

  matrix operator *(matrix other){
    matrix sol(lines, other.cols);

    for(int i = 0; i < lines; ++i)
      for(int j = 0; j < cols; ++j){
        sol.p[i][j] = 0;
        for(int k = 0; k < other.cols; ++k)
          sol.p[i][j] = (long long)(sol.p[i][j] + p[i][k] * other.p[k][j]) % kmod;
      }

    return sol;
  }

};

int fib, ans;

void read(){
  assert(freopen("kfib.in", "r", stdin));

  scanf("%d", &fib);
}

matrix lg_pow(matrix x, int pow){
  if(pow <= 1)
    return x;

  matrix aux = lg_pow(x, pow / 2);

  if(pow % 2 == 1)
    return aux * aux * x;

  return aux * aux;
}

void solve(){
  matrix tran(2, 2);
  tran.p[0][0] = 0;
  tran.p[0][1] = 1;
  tran.p[1][1] = 1;
  tran.p[1][0] = 1;

  matrix good = lg_pow(tran, fib - 1);
  matrix init(1, 2);
  init.p[0][0] = init.p[0][1] = 1;

  init = init * good;

  ans = init.p[0][0];
}

void write(){
  assert(freopen("kfib.out", "w", stdout));

  printf("%d", ans);
}

int main(){
  read();
  solve();
  write();
  return 0;
}