#include <bits/stdc++.h>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD = 666013;
vector<vector<int>> mat;

vector<vector<int>> multiply(vector<vector<int>> mat1,
                             vector<vector<int>> mat2) {
  vector<vector<int>> mult(2, vector<int>(2, 0));
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        mult[i][j] = (mult[i][j] + (mat1[i][k] * mat2[k][j])) % MOD;
      }
    }
  }
  return mult;
}

vector<vector<int>> matPower(vector<vector<int>> mat, int exp) {
  vector<vector<int>> P = {{1, 0}, {0, 1}};
  while (exp) {
    if (exp & 1)
      P = multiply(P, mat);
    mat = multiply(mat, mat);
    exp /= 2;
  }
  return P;
}

int main() {
  mat = {{0, 1}, {1, 1}};
  int N;
  fin >> N;
  vector<vector<int>> mult = matPower(mat, N - 1);
  fout << (mult[0][0] + mult[0][1]) % MOD;
  return 0;
}