#include <iostream>
#include <fstream>

std::ifstream in("kfib.in");
std::ofstream out("kfib.out");

long long matf[2][2]={1,1,1,0},aux[2][2]={1,0,0,1},fibo[2][2]={1,0,0,0};
const int MOD=666013;

void inmulteste(long long m1[2][2],long long m2[2][2],long long rez[2][2],int caz=0){
    long long aur[2][2];
    if(caz==0){
        aur[0][0]=m1[0][0]*m2[0][0]+m1[0][1]*m2[1][0];
        aur[0][1]=m1[0][0]*m2[1][0]+m1[0][1]*m2[1][1];
        aur[1][0]=m1[1][0]*m2[0][0]+m1[1][1]*m2[1][0];
        aur[1][1]=m1[1][0]*m2[0][1]+m1[1][1]*m2[1][1];
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                rez[i][j]=aur[i][j]%MOD;
    }
    else{
        aur[0][0]=m1[0][0]*m2[0][0]+m1[0][1]*m2[1][0];
        aur[1][0]=m1[1][0]*m2[0][0]+m1[1][1]*m2[1][0];
        rez[0][0]=aur[0][0]%MOD;
        rez[1][0]=aur[1][0]%MOD;
    }
}

void lgPut(int n){
    while(n){
        if(n%2)
            inmulteste(aux,matf,aux);
        inmulteste(matf,matf,matf);
        n/=2;
    }
}

int main(){
    int k;
    in>>k;
    lgPut(k-1);

    inmulteste(aux,fibo,aux,1);

    out<<aux[0][0];
    return 0;
}