#include <fstream>
using namespace std;

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

const int MOD = 666013;

int k;

struct Mat{

    long long mat[2][2];

};

const Mat nullMat = {
    {{1,0},
     {0,1}}
};

const Mat initMat = {

    {{0,1},
     {1,1}}
};

Mat prod( Mat a , Mat b ){

    Mat aux;

    aux.mat[0][0] = ((a.mat[0][0] * b.mat[0][0])%MOD + (a.mat[0][1] * b.mat[1][0])%MOD)%MOD;
    aux.mat[0][1] = ((a.mat[0][0] * b.mat[0][1])%MOD + (a.mat[0][1] * b.mat[1][1])%MOD)%MOD;
    aux.mat[1][0] = ((a.mat[1][0] * b.mat[0][0])%MOD + (a.mat[1][1] * b.mat[1][0])%MOD)%MOD;
    aux.mat[1][1] = ((a.mat[1][0] * b.mat[0][1])%MOD + (a.mat[1][1] * b.mat[1][1])%MOD)%MOD;

    return aux;
}

Mat pwr(Mat aux , int p){

    if(!p) return nullMat;

    if(p%2) return prod(pwr(aux,p-1),aux);

    else{

        return pwr(prod(aux,aux),p/2);
    }
}

int main(){

    cin >> k;

    cout << pwr(initMat,k).mat[0][1];

    return 0;
}