#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;
int k, a[2][2];

void f(int a[2][2], int b[2][2]) {
  int c[2][2];
  c[0][0] = c[1][1] = c[0][1] = c[1][0] = 0;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        c[i][j] = ((long long)a[i][k] * b[k][j] + c[i][j]) % MOD;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      a[i][j] = c[i][j];
}

int logpow (int n) {
  int b[2][2];
  b[0][0] = b[1][1] = 1;
  b[0][1] = b[1][0] = 0;
  while (n) {
    if (n & 1)
      f(b, a);
    f(a, a);
    n = (n >> 1);
  }
  return b[1][1];
}

int main()
{
  fin >> k;
  a[0][0] = 0;
  a[0][1] = a[1][0] = a[1][1] = 1;
  fout << logpow(k - 1);
  return 0;
}