#include <iostream>
#include <fstream>

using namespace std;

ifstream in("fibonacci.in");
ofstream out("fibonacci.out");

int const MODULO = 666013;

struct Matrix {
  int mat[2][2];
};

Matrix computeMult(Matrix a, Matrix b) {
  Matrix result;
  for(int i = 0;i < 2;i++) {
    for(int j = 0;j < 2;j++) {
      result.mat[i][j] = 0;
      for(int k = 0;k < 2;k++) {
        result.mat[i][j] = (result.mat[i][j] + 1LL * a.mat[i][k] * b.mat[k][j]) % MODULO;
      }
    }
  }
  return result;
}

Matrix logPow(Matrix a, int b) {
  if(b == 1) {
    return a;
  }else {
    Matrix mult = logPow(a, b/2);
    mult = computeMult(mult, mult);
    if(b % 2 == 0) {
      return mult;
    }else {
      return computeMult(mult, a);
    }
  }
}

int main() {

  int n;
  in >> n;
  if(n == 0) {
    out << 0;
  }else {
    Matrix expo;
    expo.mat[0][0] = 0;
    expo.mat[0][1] = 1;
    expo.mat[1][0] = 1;
    expo.mat[1][1] = 1;
    expo = logPow(expo, n);
    out << expo.mat[1][0] << '\n';
  }
  return 0;
}