#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
const int mod = 666013;

void mat_mult(int res[2][2], int a[2][2]) {
  int tmp[2][2];

  rep(i,2)
  rep(j,2) {
    tmp[i][j] = (1ll*res[i][0]*a[0][j] + 1ll*res[i][1]*a[1][j]) % mod;
  }

  memcpy(res, tmp, sizeof(tmp));
}

void mat_square(int res[2][2]) {
  int tmp[2][2];
  rep(i,2)
  rep(j,2) {
    tmp[i][j] = (1ll*res[i][0]*res[0][j] + 1ll*res[i][1]*res[1][j]) % mod;
  }

  memcpy(res, tmp, sizeof(tmp));
}

int main(void) {
  // freopen("kfib.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);

  int k;
  fin >> k;
  int a[2][2] = {{1,1}, {1,0}}; // fibonaccu recurrence
  int res[2][2] = {{1,0}, {0,1}}; // ID matrix

  while(k > 0) {
    if (k & 1) {
      mat_mult(res, a);
    }
    k /= 2;
    mat_square(a);
  }
  fout << res[0][1] << '\n';

  return 0;
}