#include <iostream>
#include <cstdio>
#define MOD 666013

using namespace std;

struct matrix {
  long long a[5][5];

  matrix() {
    a[1][1] = a[1][2] = a[2][1] = a[2][2] = 0;
  }

  matrix operator * (matrix);
  void fast_pow(long long);
} I;

matrix matrix::operator * (matrix b) {
  matrix c;

  for(int i = 1; i <= 2; i++)
    for(int j = 1; j <= 2; j++)
      for(int k = 1; k <= 2; k++)
        c.a[i][j] = (c.a[i][j] + (this->a[i][k] * b.a[k][j]) % MOD) % MOD;
  return c;
}

void matrix::fast_pow(long long pow) {
  matrix r = I;
  if(pow == 0)
    *this = I;

  while(pow > 1) {
    if(pow & 1)
      r = r * *this;
    *this = *this * *this;
    pow >>= 1;
  }
  *this = *this * r;
}

long long n;

int main() {
  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);

  scanf("%lld", &n);

  matrix M, ans;
  M.a[1][2] = M.a[2][1] = M.a[2][2] = 1;
  I.a[1][1] = I.a[2][2] = 1;
  ans.a[1][2] = 1;

  if(n == 0)
    printf("0");
  else if(n == 1)
    printf("1");
  else {
    M.fast_pow(n - 1);
    ans = ans * M;
    printf("%lld", ans.a[1][2]);
  }

  return 0;
}