#include <stdio.h>
#define MOD 666013
int n, m[2][2];
inline void inmultire(int a[2][2], int b[2][2]){
    int i, j, k, aux[2][2];
    aux[0][0]=aux[1][0]=aux[0][1]=aux[1][1]=0;
    for(i=0; i<2; i++){
        for(j=0; j<2; j++){
            for(k=0; k<2; k++){
                aux[i][j]=(1LL*aux[i][j]+1LL*a[i][k]*b[k][j])%MOD;
            }
        }
    }
    for(i=0; i<2; i++){
        for(j=0; j<2; j++){
            a[i][j]=aux[i][j];
        }
    }
}
inline void lgput(int n){
    int p[2][2];
    m[0][0]=m[1][1]=1;
    p[0][0]=0;
    p[1][0]=p[0][1]=p[1][1]=1;
    while(n!=0){
        if((n&1)==1){
            inmultire(m, p);
        }
        inmultire(p, p);
        n>>=1;
    }
}
int main(){
    int n;
    FILE *fin, *fout;
    fin=fopen("kfib.in", "r");
    fout=fopen("kfib.out", "w");
    fscanf(fin, "%d", &n);
    lgput(n-1);
    fprintf(fout, "%d\n", m[1][1]);
    fclose(fin);
    fclose(fout);
    return 0;
}