#include<cstdio>
#define mod 666013
long long k,i,j,x[10][10],b[10][10],sol[10][10];
FILE *f,*g;
void prod(long long a[10][10],long long b[10][10],long long x[10][10]){
    long long i,j,k;
    for(i=1;i<=2;i++){
        for(j=1;j<=2;j++){
            x[i][j]=0;
        }
    }
    for(i=1;i<=2;i++){
        for(j=1;j<=2;j++){
            for(k=1;k<=2;k++){
                x[i][j]=(x[i][j]+(a[i][k]*b[k][j])%mod)%mod;
            }
        }
    }
    return;
}
int main(){
    f=fopen("kfib.in","r");
    g=fopen("kfib.out","w");
    fscanf(f,"%d",&k);
    k-=2;
    sol[1][1]=x[1][1]=x[2][1]=x[1][2]=sol[2][2]=1;
    while(k!=0){
        if(k%2==1){
            prod(sol,x,b);
            sol[1][1]=b[1][1];
            sol[1][2]=b[1][2];
            sol[2][1]=b[2][1];
            sol[2][2]=b[2][2];
        }
        prod(x,x,b);
        x[1][1]=b[1][1];
        x[1][2]=b[1][2];
        x[2][1]=b[2][1];
        x[2][2]=b[2][2];
        k/=2;
    }
    fprintf(g,"%lld",(sol[1][1]+sol[1][2])%mod);

    fclose(f);
    fclose(g);
    return 0;
}