#include<stdio.h>
#define DIM 5
#define RTT 666013
FILE *f=fopen("kfib.in","r"), *g=fopen("kfib.out","w");

long int K, Z[DIM][DIM], r[DIM][DIM];

void citire(){
    fscanf(f,"%ld\n",&K);
}

void initializare(){

    Z[1][1]=0; Z[1][2]=1; Z[2][1]=1; Z[2][2]=1; // 0 1
    r[1][1]=0; r[1][2]=1; r[2][1]=1; r[2][2]=1; // 1 1

}

void inmultire(long int a[DIM][DIM], long int b[DIM][DIM]){
long long int e1, e2, e3, e4;

    e1= 1LL * a[1][1] * b[1][1] + 1LL * a[1][2] * b[2][1];
    e2= 1LL * a[1][1] * b[1][2] + 1LL * a[1][2] * b[2][2];
    e3= 1LL * a[2][1] * b[1][1] + 1LL * a[2][2] * b[2][1];
    e4= 1LL * a[2][1] * b[1][2] + 1LL * a[2][2] * b[2][2];

    a[1][1]= (long int)(e1%RTT); a[1][2]= (long int)(e2%RTT);
    a[2][1]= (long int)(e3%RTT); a[2][2]= (long int)(e4%RTT);

}

void rezolvare(){

    // Z^(K-1) % RTT
    K-=2;
    while(K!=0){

        if(K%2==1){ inmultire(r,Z); }
        inmultire(Z,Z); K/=2;

    }

    fprintf(g,"%ld\n",r[2][2]);

}

int main(){

    citire();
    initializare();
    rezolvare();

return 0;
}