#include<stdio.h>
long k,a[3][3],rez[3][3],ca[3][3],crez[3][3];
void prod (){
    int i,j;
    a[1][1]=0;
    a[1][2]=a[2][1]=a[2][2]=1;
    rez[1][1]=rez[2][2]=1;
    rez[1][2]=rez[2][1]=0;
    k=k-2;
    while(k!=0){
        if(k%2==1){
            k--;
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    crez[i][j]=rez[i][j];
            rez[1][1]=((crez[1][1]*a[1][1])%666013+(crez[1][2]*a[2][1])%666013)%666013;
            rez[1][2]=((crez[1][1]*a[1][2])%666013+(crez[1][2]*a[2][2])%666013)%666013;
            rez[2][1]=((crez[2][1]*a[1][1])%666013+(crez[2][2]*a[2][1])%666013)%666013;
            rez[2][2]=((crez[2][1]*a[1][2])%666013+(crez[2][2]*a[2][2])%666013)%666013;
        }
        else{
            k=k/2;
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    ca[i][j]=a[i][j];
            a[1][1]=((ca[1][1]*ca[1][1])%666013+(ca[1][2]*ca[2][1])%666013)%666013;
            a[1][2]=((ca[1][1]*ca[1][2])%666013+(ca[1][2]*ca[2][2])%666013)%666013;
            a[2][1]=((ca[2][1]*ca[1][1])%666013+(ca[2][2]*ca[2][1])%666013)%666013;
            a[2][2]=((ca[2][1]*ca[1][2])%666013+(ca[2][2]*ca[2][2])%666013)%666013;
        }
    }
    printf("%ld\n",(rez[1][2]+rez[2][2])%666013);
}
int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%ld",&k);
    prod();
    return 0;
}