#include <bits/stdc++.h>

using namespace std;

const string fisier = "kfib";

ifstream fin (fisier + ".in");
ofstream fout (fisier + ".out");

typedef int MatFib[2][2];

const int mod = 666013;

void Produs(MatFib A , MatFib B, MatFib P)
{
    P[0][0] = (1LL * A[0][0] * B[0][0] + 1LL * A[0][1] * B[1][0]) % mod;
    P[0][1] = (1LL * A[0][0] * B[0][1] + 1LL * A[0][1] * B[1][1]) % mod;
    P[1][0] = (1LL * A[1][0] * B[0][0] + 1LL * A[1][1] * B[1][0]) % mod;
    P[1][1] = (1LL * A[1][0] * B[0][1] + 1LL * A[1][1] * B[1][1]) % mod;
}

void Atrib(MatFib D ,MatFib S)
{
    D[0][0] = S[0][0];
    D[0][1] = S[0][1];
    D[1][0] = S[1][0];
    D[1][1] = S[1][1];
}

int solve (int n){
  MatFib A = {{1 , 1} , {1 , 0}} , B , R = {{1 , 0} , {0 , 1}};
  while (n > 0){
    if (n & 1){
      Produs(R , A , B);
      Atrib(R , B);
    }
    Produs(A , A , B);
    Atrib(A , B);
    n >>= 1;
  }
  return R[0][1];
}

void test_case() {
  int n; fin >> n;
  fout << solve(n);
}

int main(){
  ios_base::sync_with_stdio(false);
  int tests = 1;
  for (int tc=0; tc<tests; ++tc) {
    test_case();
  }
}