#include <cstdio>
#include <iostream>
#include <fstream>

using namespace std;

const long MOD = 666013;

long long orig[2][2] = {
  {0, 1},
  {1, 1}
};

void mat_mult(long long a[2][2], long long b[2][2], long long c[2][2]) {
  long long n = 2;

  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++)
      c[i][j] = 0;

  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++)
      for (long long k = 0; k < n; k++)
        c[i][j] = (c[i][j] + (a[i][k] * b[k][j]) % MOD) % MOD;
}

void mat_copy(long long a[2][2], long long b[2][2], long long n) {
  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++)
      a[i][j] = b[i][j];
}

void print_mat(long long a[2][2], long long n) {
  for (long long i =0; i < n; i++) {
    for (long long j = 0; j < n; j++)
      printf("%d ", a[i][j]);
    printf("\n");
  }
}

void mat_pow(long long a[2][2], long long n) {
  //  cout << n << endl;
  if (n == 1)
    return;
  mat_pow(a, n/2);
  //  print_mat(a, 2);

  long long c[2][2];
  mat_mult(a, a, c);
  mat_copy(a, c, 2);
  // printf("Mat mult:\n");
  // print_mat(a, 2);
  // printf("Mat mult\n");

  if (n % 2 == 1)
    mat_mult(a, orig, c);
  mat_copy(a, c, 2);
}



int main()
{

  long long a [2][2] = {
    {0, 1},
    {1, 1}
  };

  long long b[2][2] = {
    {1, 1},
    {1, 2}
  };

  long long c[2][2] = {
    {0, 0},
    {0, 0}
  };


  ifstream f("kfib.in");
  ofstream g("kfib.out");

  long long k;
  f >> k;
  mat_pow(a, k);
  g << a[0][1] << endl;
  return 0;
}