#include <stdio.h>

#define MOD 666013

void inmultesteMatrici(long long a[4],long long b[4],long long rezultat[4]){
    long long temp[4];
    temp[0]=(a[0]*b[0]+a[1]*b[2])%MOD;
    temp[1]=(a[0]*b[1]+a[1]*b[3])%MOD;
    temp[2]=(a[2]*b[0]+a[3]*b[2])%MOD;
    temp[3]=(a[2]*b[1]+a[3]*b[3])%MOD;

    for(int i=0;i<4;i++){
        rezultat[i]=temp[i];
    }
}

void putereMatrice(long long Z[4],long long exponent,long long rezultat[4]){
    rezultat[0]=1; 
    rezultat[1]=0;
    rezultat[2]=0; 
    rezultat[3]=1;

    long long baza[4];
    for(int i=0;i<4;i++){
        baza[i]=Z[i];
    }

    while(exponent>0){
        if(exponent%2==1){
            inmultesteMatrici(rezultat, baza, rezultat);
        }
        inmultesteMatrici(baza, baza, baza);
        exponent=exponent/2;
    }
}

int main(){

    FILE *fin=fopen("kfib.in","r");
    FILE *fout=fopen("kfib.out","w");
    long long K;
    fscanf(fin,"%lld",&K);
    if(K==0){
        fprintf(fout,"0\n");
    } else if(K==1){
        fprintf(fout,"1\n");
    } else {
        long long Z[4] = {0,1,1,1};
        long long Zk[4];
        putereMatrice(Z,K-1,Zk);
        long long Fk=Zk[3];

        fprintf(fout,"%lld\n",Fk);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}