#include <cstdio>
using namespace std;

const long long MOD=666013;

long long F[64][2][2];

int logar(long k){
        int l=0;
        if((0xFFFF0000&k))
                k>>=16,l+=16;
        if((0xFF00&k))
            k>>=8,l+=8;
        if((0xF0&k))
            k>>=4,l+=4;
        if((12&k))
            k>>=2,l+=2;
        if(k>1)
            l+=1;
        return  l;
}

void poweM(long k){
    int i,l=logar(k),temp[4];
    for(i=1;i<=l;i++){
        //F[i]=F[i-1]^2
        F[i][0][0]=(F[i-1][0][0]*F[i-1][0][0]+F[i-1][0][1]*F[i-1][1][0])%MOD;
        F[i][0][1]=(F[i-1][0][0]*F[i-1][0][1]+F[i-1][0][1]*F[i-1][1][1])%MOD;
        F[i][1][0]=(F[i-1][1][0]*F[i-1][0][0]+F[i-1][1][1]*F[i-1][1][0])%MOD;
        F[i][1][1]=(F[i-1][1][0]*F[i-1][0][1]+F[i-1][1][1]*F[i-1][1][1])%MOD;
    }
    F[60][0][0]=F[60][1][1]=1;
    i=0;
    while(k){
          if((k&1)){
                    temp[0]=((F[60][0][0]*F[i][0][0])%MOD+(F[60][0][1]*F[i][1][0])%MOD)%MOD;
                    temp[1]=((F[60][0][0]*F[i][0][1])%MOD+(F[60][0][1]*F[i][1][1])%MOD)%MOD;
                    temp[2]=((F[60][1][0]*F[i][0][0])%MOD+(F[60][1][1]*F[i][1][0])%MOD)%MOD;
                    temp[3]=((F[60][1][0]*F[i][0][1])%MOD+(F[60][1][1]*F[i][1][1])%MOD)%MOD;
                    F[60][0][0]=temp[0];
                    F[60][0][1]=temp[1];
                    F[60][1][0]=temp[2];
                    F[60][1][1]=temp[3];
            }
            k>>=1;
            i++;
    }
}

long fibo(long k)
{
    if(k<2) return k;
    poweM(k-1);
    return F[60][0][0];
}

int main()
{
    long long k, tk;
    FILE* f,*g;
    f=fopen("kfib.in","r");
    fscanf(f,"%ld",&k);
    fclose(f);
    F[0][0][0]=F[0][0][1]=F[0][1][0]=1;
    tk=fibo(k);
    g=fopen("kfib.out","w");
    fprintf(g, "%lld", tk);
    fclose(g);
    return 0;
}