#include <cstdio>

int k,p,a[2][2],rez[2][2],i,j,sol,out[2][2];

void prod(int in1[][2],int in2[][2])
{
    int i,j,k;
    for (i=0;i<2;++i)
        for (j=0;j<2;++j)
            for (k=0;k<2;++k)
                out[i][j]=(out[i][j]+1LL*in1[i][k]*in2[k][j])%666013;
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&k);
    if (k<2)
    {
        printf("%d",k);
        return 0;
    }
    a[0][1]=a[1][0]=a[1][1]=1;
    rez[0][0]=rez[1][1]=1;
    for (p=k-1;p;p>>=1)
    {
        if (p & 1)
        {
            out[0][0]=out[0][1]=out[1][0]=out[1][1]=0;
            prod(rez,a);
            rez[0][0]=out[0][0],rez[0][1]=out[0][1],rez[1][0]=out[1][0],rez[1][1]=out[1][1];
        }
        out[0][0]=out[0][1]=out[1][0]=out[1][1]=0;
        prod(a,a);
        a[0][0]=out[0][0],a[0][1]=out[0][1],a[1][0]=out[1][0],a[1][1]=out[1][1];
    }
    printf("%d",rez[1][1]);
    return 0;
}