#include  <iostream>
#include  <fstream>
#define ll long long

using namespace std;

const int mod = 666013;

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

int RezF[3][3],
 C[3][3];
int A[3][3];
int F[2][2];

void InmultireMat(int A[][3], int B[][3]) {
  C[1][1] = (1LL * A[1][1] * B[1][1] + 1LL * A[1][2] * B[2][1]) % mod;
  C[1][2] = (1LL * A[1][1] * B[1][2] + 1LL * A[1][2] * B[2][2]) % mod;
  C[2][1] = (1LL * A[2][1] * B[1][1] + 1LL * A[2][2] * B[2][1]) % mod;
  C[2][2] = (1LL * A[2][1] * B[1][2] + 1LL * A[2][2] * B[2][2]) % mod;
}

void Copy (int A[][3], int B[][3]) {
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++)
      A[i][j] = B[i][j];
}

void lgput(int exp) {
  int B[3][3];
  while(exp){
    if (exp & 1) {
      InmultireMat(A, RezF);
      Copy(RezF, C);
    }
    InmultireMat(A, A);
    Copy(A, C);
    exp >>= 1;
  }

}

int main() {
  int x;
  A[1][2] = A[2][1] = A[2][2] = RezF[1][1] = RezF[2][2] = F[1][2] = 1;
  in>>x;
  lgput(x - 1);
  F[1][2] = RezF[1][2], F[2][1] = RezF[2][2];
  out<<F[2][1];
}