/* 
 * File:   AlkleatermenFibonacci.cpp
 * Author: slycer
 *
 * Created on January 1, 2012, 9:00 PM
 */

#include <cstdlib>
#include <fstream>
#include <iostream>

using namespace std;

class Matrix{
public:
    static const int MOD= 666013;
    long long data[2][2];
    
    Matrix(){
    }
    
   static Matrix add( Matrix a, Matrix b){
        Matrix ret; 
        for ( int i=0; i<2; i++){
            for ( int j=0; j<2; j++){
                ret.data[i][j] = (a.data[i][j] + b.data[i][j])%MOD;
            }
        }
    }
    
    static Matrix pow( Matrix a, int k ){
        if ( k==1 ){
            return a; 
        }
        if ( k % 2 == 0 ){
            Matrix ret = pow(a,k/2);
            return mult(ret,ret);
        } else {
            Matrix ret = pow(a,k-1);
            return mult(a,ret);
        }
    }
    
    static Matrix mult( Matrix a, Matrix b ){
        Matrix ret; 
        for ( int i=0; i<2; i++){
            for ( int j=0; j<2; j++){
                ret.data[i][j] = 0; 
                for ( int k=0; k<2; k++){
                    ret.data[i][j] += a.data[i][k]*b.data[k][j];
                }
                ret.data[i][j]= ret.data[i][j]%MOD;
            }
        }
        return ret; 
    }
};

/*
 * 
 */
int main(int argc, char** argv) {

    ifstream input("kfib.in");
    ofstream output("kfib.out");
    
    int k;
    input >> k; 
    
    Matrix a;
    a.data[0][0] = 1; 
    a.data[0][1] = 1; 
    Matrix base; 
    base.data[0][0] = 0; 
    base.data[1][1] = 1; 
    base.data[1][0] = 1; 
    base.data[0][1] = 1; 
    
    if ( k==0 || k==1 ){
        output << "1";
    } else {
        Matrix rez = Matrix::pow( base,k-2 );
        rez = Matrix::mult( a, rez );
        int sol = rez.data[0][1]; 
        output << sol; 
    }
    
    
    return 0;
}