#include <fstream>

using namespace std;

const long modulo = 666013;

void setZero(long long int mat[2][2]){ 
     for (int i=0;i<2;i++)
         for (int j=0;j<2;j++) 
             mat[i][j] = 0 ;
}

void copy(long long int dest[2][2], long long src[2][2]){
    for (int i=0;i<2;i++)
         for (int j=0;j<2;j++) 
             dest[i][j] = src[i][j] ;
}

void multMat22(long long mat1[2][2], long long mat2[2][2] ){
     long long aux[2][2];
     setZero(aux);
     for (int i=0;i<2;i++)
       for (int j=0;j<2;j++)
         for (int k=0;k<2;k++)
           aux[i][j] = ( aux[i][j] + (mat1[i][k] * mat2[k][j]) % modulo ) %modulo; 
     copy(mat1, aux);
}


void matPow(long long mat[2][2],long long n){
     if (n <= 1) return;
     else{
     if ( n % 2 == 0 ){
            matPow(mat, n/2);
            multMat22(mat,mat);
            return ;
        }
     else {
            long long aux[2][2];
            copy(aux, mat);
            matPow(mat, (n - 1)/2);
            multMat22(mat,mat);
            multMat22(mat,aux);
            return ;
          }
     }
}

int main(){
    long long k;
    
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    long long z[2][2] = { {0,1}, {1,1}};
       
    f >> k;
    if ( k == 0 ) { g << "0" << endl; goto end;} 

    matPow(z, k-1);
    g << z[1][1] << endl;

    end:
    f.close();
    g.close();
    return 0;
}