#include <stdio.h>
#include <stdlib.h>
#define BIGPRIME 666013
int main(){
    FILE*fi,*fout;
    long long a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,aux1,aux2,aux3,aux4,exp,k;
    fi=fopen("kfib.in" ,"r");
    fout=fopen("kfib.out" ,"w");
    fscanf(fi,"%lld" ,&k);
    a1=b1=0;
    a2=a3=a4=b2=b3=b4=1;
    exp=k-2;
    c1=c2=c3=c4=1;
    while(exp>0){
        if(exp%2==1){
            aux1=(c1*a1+c2*a3)%BIGPRIME;
            aux2=(c1*a2+c2*a4)%BIGPRIME;
            aux3=(c3*a1+c4*a3)%BIGPRIME;
            aux4=(c3*a2+c4*a4)%BIGPRIME;
            c1=aux1;
            c2=aux2;
            c3=aux3;
            c4=aux4;
        }
        b1=(a1*a1+a2*a3)%BIGPRIME;
        b2=(a1*a2+a2*a4)%BIGPRIME;
        b3=(a3*a1+a4*a3)%BIGPRIME;
        b4=(a3*a2+a4*a4)%BIGPRIME;
        a1=b1;
        a2=b2;
        a3=b3;
        a4=b4;
        exp=exp/2;
    }
    fprintf(fout,"%lld" ,c4);
    fclose(fi);
    fclose(fout);
    return 0;
}