#include <stdio.h>
#include <stdlib.h>

#define fin "kfib.in"
#define fout "kfib.out"

#define mod 666013

void print_array(int a[],int l,int c){
    for(int i=0;i<l*c;++i){
        printf("%d ",a[i]);
        if((i+1)%c==0 && c!=1){
            printf("\n");
        }
    }
    printf("\n");
}

void pow2_size2_matrix(long long a[]){
    long long b[4];
    for(int i=0;i<4;++i){
        b[i]=a[i];
    }
    a[0]=(b[0]*b[0]+b[1]*b[2])%mod;
    a[1]=(b[0]*b[1]+b[1]*b[3])%mod;
    a[2]=(b[2]*b[0]+b[3]*b[2])%mod;
    a[3]=(b[2]*b[1]+b[3]*b[3])%mod;
}

int log_exp(int f[],long long a[],int k){
    if(k==0){
        return f[0];
    }
    if(k%2){
        int e[2];
        e[0]=f[0];
        e[1]=f[1];
        f[0]=(e[0]*a[0]+e[1]*a[2])%mod;
        f[1]=(e[0]*a[1]+e[1]*a[3])%mod;
        pow2_size2_matrix(a);
        return log_exp(f,a,(k-1)/2);
    }
    else{
        pow2_size2_matrix(a);
        return log_exp(f,a,k/2);
    }
}

int main()
{
    FILE *f,*g;
    f=fopen(fin,"r");
    g=fopen(fout,"w");
    int k,fib[]={0,1};
    long long a[]={0,1,1,1};
    fscanf(f,"%d",&k);
    fprintf(g,"%d\n",log_exp(fib,a,k));
    fclose(f);
    fclose(g);
    return 0;
}