#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
typedef long long int64;
const int HELL = 666013;

int kfib(int k);
void multiply(int64 A[][2], int64 B[][2]);
inline int mod(int64 x, int m);

int main() {
  int K;
  fin >> K;
  fout << kfib(K);
  return 0;
}

int kfib(int k) {
  int64 fib_matrix[2][2] = {{1, 1}, {1, 0}};
  int64 log2_p[2][2] = {{1, 1}, {1, 0}};

  for (int p = 1; p <= k; p *= 2) {
    if (p & k) {
      multiply(fib_matrix, log2_p);
    }
    multiply(log2_p, log2_p);
  }
  return fib_matrix[1][1];
}

void multiply(int64 A[][2], int64 B[][2]) {
  int a = mod(mod(A[0][0] * B[0][0], HELL) + mod(A[0][1] * B[1][0], HELL), HELL);
  int b = mod(mod(A[0][0] * B[0][1], HELL) + mod(A[0][1] * B[1][1], HELL), HELL);
  int c = mod(mod(A[1][0] * B[0][0], HELL) + mod(A[1][1] * B[1][0], HELL), HELL);
  int d = mod(mod(A[1][0] * B[0][1], HELL) + mod(A[1][1] * B[1][1], HELL), HELL);
  A[0][0] = a;
  A[0][1] = b;
  A[1][0] = c;
  A[1][1] = d;
}

inline int mod(int64 x, int m) {
  if (x < m) return x;
  if (x < 2 * m) return x - m;
  return x % m;
}