#include <bits/stdc++.h>
using namespace std;

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

using namespace std;

long long MOD = 666013;

struct Matrix {
  long long mat[2][2];
  Matrix() { mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0; }
};

Matrix multiply(Matrix A, Matrix B) {
  Matrix C;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
  return C;
}

Matrix power(Matrix A, long long p) {
  Matrix res;
  res.mat[0][0] = 1;
  res.mat[1][1] = 1; // Matricea identitate
  while (p > 0) {
    if (p & 1)
      res = multiply(res, A);
    A = multiply(A, A);
    p >>= 1;
  }
  return res;
}

int main() {
  long long n, a = 1, b = 1;
  fin >> n;

  if (n == 1 || n == 2) {
    fout << 1 << endl;
    return 0;
  }

  Matrix T;
  T.mat[0][0] = a % MOD;
  T.mat[0][1] = b % MOD;
  T.mat[1][0] = 1;
  T.mat[1][1] = 0;

  T = power(T, n - 2);

  long long result = (T.mat[0][0] + T.mat[0][1]) % MOD;

  fout << result << endl;

  return 0;
}