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


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