#include <stdio.h>
#define mod 666013
#define lim 2
int baza[lim][lim],rez[lim][lim],cop[lim][lim];
void produs(int a[lim][lim],int b[lim][lim],int c[lim][lim]){
    int i,j,k;
    //c[lim][lim]={0};
    for(i=0;i<lim;i++)
        for(j=0;j<lim;j++) {
            c[i][j]=0;
            for(k=0;k<lim;k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%mod;
        }
}
void copiere(int a[lim][lim],int b[lim][lim]){
    int i,j;
    for(i=0;i<lim;i++)
        for(j=0;j<lim;j++)
            b[i][j]=a[i][j];
}
void putlog(int exp){
    while(exp!=0){
        if(exp%2==1){
            produs(rez,baza,cop);
            copiere(cop,rez);
        }
        produs(baza,baza,cop);
        copiere(cop,baza);
        exp/=2;
    }
}
int main(){
    FILE *fin,*fout;
    fin=fopen("kfib.in","r");
    fout=fopen("kfib.out","w");
    int n;
    fscanf(fin,"%d",&n);
    baza[0][0]=baza[0][1]=baza[1][0]=1;
    baza[1][1]=0;
    rez[0][0]=rez[1][1]=1;
    rez[0][1]=rez[1][0]=0;
    putlog(n-1);
    fprintf(fout,"%d",rez[0][0]);
    fclose(fin);
    fclose(fout);
    return 0;
}