#include<stdio.h>
#define mod 666013
long long  k,a[3][3],rez[3][3],a1[3][3],rez1[3][3];
void calc (){
    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++)
                    rez1[i][j]=rez[i][j];
            rez[1][1]=((rez1[1][1]*a[1][1])%mod+(rez1[1][2]*a[2][1])%mod)%mod;
            rez[1][2]=((rez1[1][1]*a[1][2])%mod+(rez1[1][2]*a[2][2])%mod)%mod;
            rez[2][1]=((rez1[2][1]*a[1][1])%mod+(rez1[2][2]*a[2][1])%mod)%mod;
            rez[2][2]=((rez1[2][1]*a[1][2])%mod+(rez1[2][2]*a[2][2])%mod)%mod;
        }
        else{
            k=k/2;
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    a1[i][j]=a[i][j];
            a[1][1]=((a1[1][1]*a1[1][1])%mod+(a1[1][2]*a1[2][1])%mod)%mod;
            a[1][2]=((a1[1][1]*a1[1][2])%mod+(a1[1][2]*a1[2][2])%mod)%mod;
            a[2][1]=((a1[2][1]*a1[1][1])%mod+(a1[2][2]*a1[2][1])%mod)%mod;
            a[2][2]=((a1[2][1]*a1[1][2])%mod+(a1[2][2]*a1[2][2])%mod)%mod;
        }
    }
    printf("%lld\n",(rez[1][2]+rez[2][2])%mod);
}
int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%lld",&k);
    calc();
    return 0;
}