#include <fstream>
#include <vector>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

typedef long long ll;
#define matrix vector<vector<int>>
const int MOD = 666013;

int add(int a, int b) {
  a += b;
  if (a >= MOD) {
    return a - MOD;
  }
  if (a < 0) {
    return a + MOD;
  }
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % MOD;
}

matrix build(int n, int m) {
  matrix a;
  a.resize(n);
  for (int i = 0; i < n; i++) {
    a[i].resize(m, 0);
  }
  return a;
}

matrix mult1(matrix a, matrix b) { /// o(n ^ 2)
  /// a(1, n)
  /// b(n, n)
  /// i = 0

  int n = (int) b.size();
  matrix c = build(1, n);
  for (int j = 0; j < n; j++) {
    for (int k = 0; k < n; k++) {
      c[0][j] = add(c[0][j], mul(a[0][k], b[k][j]));
    }
  }
  return c;
}

matrix mult2(matrix a, matrix b) { /// o(n ^ 3)
  /// a(n, n)
  /// b(n, n)

  int n = (int) b.size();
  matrix c = build(n, n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
      }
    }
  }
  return c;
}

matrix pw(matrix a, int k) {
  int n = (int) a.size();
  matrix sol = build(n, n);
  for (int i = 0; i < n; i++) {
    sol[i][i] = 1;
  }
  while (k) {
    if (k & 1) {
      sol = mult2(sol, a);
    }
    a = mult2(a, a);
    k /= 2;
  }
  return sol;
}

matrix sol, base;
/// sol * base ^ k

int solve(int k) {
  base = pw(base, k - 1);
  sol = mult1(sol, base);
  return sol[0][1];
}


int main() {
  int k;
  cin >> k;
  base = build(2, 2);
  base[0][1] = base[1][0] = base[1][1] = 1;
  sol = build(1, 2);
  sol[0][1] = 1;
  cout << solve(k) << "\n";
}