#include <stdio.h>
#define mod 666013

typedef struct {
    int m[2][2];
}matrice;

matrice inmultire(matrice A, matrice B)
{
    matrice C;
    C.m[0][0]=(1LL*A.m[0][0]*B.m[0][0]+1LL*A.m[0][1]*B.m[1][0])%mod;
    C.m[0][1]=(1LL*A.m[0][0]*B.m[0][1]+1LL*A.m[0][1]*B.m[1][1])%mod;
    C.m[1][0]=(1LL*A.m[1][0]*B.m[0][0]+1LL*A.m[1][1]*B.m[1][0])%mod;
    C.m[1][1]=(1LL*A.m[1][0]*B.m[0][1]+1LL*A.m[1][1]*B.m[1][1])%mod;
    return C;
}


//ridicarea la putere in timp logaritmic pentru matrici

matrice power(matrice A, int p)
{ 
    matrice sol = {{{1, 0}, {0, 1}}};
    while(p>0)
    {
        if(p%2==1)
        sol=inmultire(sol,A);
        A=inmultire(A,A);
        p=p/2;
    }
    return sol;
}

int main(void)
{
    FILE *f1=NULL, *f2=NULL;
    f1=fopen("kfib.in","r");
    f2=fopen("kfib.out","w");
    int k;
    fscanf(f1,"%d", &k);
    fclose(f1);

    if (k==0)
    {
        fprintf(f2,"0\n");
    }

    matrice Z={{{1, 1}, {1, 0}}};
    matrice rezultat=power(Z,k-1);
    fprintf(f2,"%d\n", rezultat.m[0][0]);
    fclose(f2);

    return 0;
}