#include<cstdio>
#define MOD 666013
long long k,i,j,x[10][10],y[10][10],s[10][10];
FILE *f,*g;
void inm(long long a[10][10],long long b[10][10],long long x[10][10]){
    long long i,j,k;
    x[1][1]=x[1][2]=x[2][1]=x[2][2]=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;
            }
        }
    }
}
int main(){
    f=fopen("kfib.in","r");
    g=fopen("kfib.out","w");
    fscanf(f,"%d",&k);
    k-=2;
    s[1][1]=s[2][2]=x[1][1]=x[1][2]=x[2][1]=1;
    while(k!=0){
        if(k%2){
            inm(s,x,y);
            s[1][1]=y[1][1];
            s[1][2]=y[1][2];
            s[2][1]=y[2][1];
            s[2][2]=y[2][2];
        }
        inm(x,x,y);
        x[1][1]=y[1][1];
        x[1][2]=y[1][2];
        x[2][1]=y[2][1];
        x[2][2]=y[2][2];
        k/=2;
    }
    fprintf(g,"%lld",( s[1][1]+s[1][2] ) % MOD );




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