#include <fstream>
#include <cstring>
#include <cstdio>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int n,i, mod = 666013;
int matrice[3][3],matrice2[3][3];

void patrat(int A[3][3], int B[3][3], int C[3][3]) {
  for(int i = 0; i < 2; i++) {
    for(int j = 0; j < 2; j++) {
      for(int k = 0; k < 2; k++) {
        C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;
      }
    }
  }
}

void power(int putere, int mat[][3]) {
    int unit[3][3];
    unit[0][0] = unit[1][1] = 1;
    unit[1][0] = unit[0][1] = 0;
    while(putere) {
      if(putere & 1) {
        memset(matrice2,0,sizeof(matrice2));
        patrat(unit,mat,matrice2);
        memcpy(unit,matrice2,sizeof(matrice2));
      }
      memset(matrice2,0,sizeof(matrice2));
      patrat(mat,mat,matrice2);
      memcpy(mat,matrice2,sizeof(matrice2));
      putere >>=1;
    }
    g << unit[1][1];
}

int main() {
    f >> n;
    matrice[0][0] = 0;
    matrice[0][1] = matrice[1][0] = matrice[1][1] = 1;
    power(n-1,matrice);
}