#include<fstream>
using namespace std;
    ifstream f("kfib.in");
    ofstream g("kfib.out");
const long modulo = 666013;
long a[2][2], A[2][2], aux[2][2];

void initializareMatrice(){
    a[0][0] = a[0][1] = a[1][0] = aux[0][0] = aux[0][1] = aux[1][0] = 1;
    a[1][1] = aux[1][1] = 0;
    A[0][0] = A[0][1] = A[1][0] = 1;
    A[1][1] = 0;
}

void inmulteste(long x[2][2], long y[2][2], long (&z)[2][2]){
    z[0][0] = (x[0][0] * y[0][0] + x[0][1] * y[1][0])%modulo;
    z[0][1] = (x[0][0] * y[0][1] + x[0][1] * y[1][1])%modulo;
    z[1][0] = (x[1][0] * y[0][0] + x[1][1] * y[1][0])%modulo;
    z[1][1] = (x[1][0] * y[0][1] + x[1][1] * y[1][1])%modulo;
}

void putere(long k){
  long aux2[2][2];
  while(k){
    if(k & 1){
        aux2[0][0]=A[0][0]; aux2[0][1]=A[0][1];aux2[1][0]=A[1][0];aux2[1][1]=A[1][1];
        inmulteste(aux2, aux, A);
        k--;
    }
    else{
        aux2[0][0]=aux[0][0]; aux2[0][1]=aux[0][1];aux2[1][0]=aux[1][0];aux2[1][1]=aux[1][1];
        inmulteste(aux2, aux2, aux);
        k = k>>1;
    }
  }
}

int main(){
long n;
f>>n;
initializareMatrice();
if(n==1) g<<1;
else if(n==2) g<<1;
else if(n==3) g<<2;
else{
putere(n-2);
g<<A[0][0];
}
return 0;
}