#include <bits/stdc++.h>

#define MOD 666013

using namespace std;

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

struct matrix
{
  unsigned long long a, b, c, d;

  matrix operator * (matrix m)
  {
    matrix n_m;
    n_m.a = (a*m.a + b*m.c) % MOD;
    n_m.b = (a*m.b + b*m.d) % MOD;
    n_m.c = (c*m.a + d*m.c) % MOD;
    n_m.d = (c*m.b + d*m.d) % MOD;

    return n_m;
  }
};

int n;

matrix power(matrix a, int b)
{
  if (b == 0)
    return (matrix) {1, 0, 0, 1};
  
  matrix c = power(a, b / 2);

  if (b % 2 == 0)
    return c * c;
  else
    return c * c * a;
}

int main() {
  fin >> n;

  matrix m = {0, 1, 1, 1};
  m = power(m, n - 2);

  fout << (m.b + m.d) % MOD;
}