#include<cstdio>
#include<cstdlib>
#include<cstring>
int k,i,mat[2][2],sol[2][2];
void mult(int a[2][2],int b[2][2],int c[2][2])
{
    int j,k;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            for(k=0;k<2;k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%666013;
}
void power(int p)
{
    int c[2][2],aux[2][2];
    memcpy(c,mat,sizeof(mat));
    sol[0][0]=sol[1][1]=1;
    for(i=0;(1<<i)<=p;i++)
    {
        if(p&(1<<i))
        {
            memset(aux,0,sizeof(aux));
            mult(sol,c,aux);
            memcpy(sol,aux,sizeof(aux));
        }
    memset(aux,0,sizeof(aux));
    mult(c,c,aux);
    memcpy(c,aux,sizeof(c));
    }
}
int main()
{
    FILE *f=fopen("kfib.in","r"),*g=fopen("kfib.out","w");
    fscanf(f,"%d",&k);
    mat[0][0]=0;mat[0][1]=mat[1][1]=mat[1][0]=1;
    power(k-1);
    fprintf(g,"%d",sol[1][1]);
    fclose(f);fclose(g);
    return 0;
}