#include <cstdio>
#define md 666013

FILE *f,*g;

long long ax[3][3];
long long a[3][3]={ 0,0,0, 0,0,1, 0,1,1};
long long sol[3][3]={ 0,0,0, 0,1,0, 0,0,1};
int n;
long long solutie;

void inm(long long a[3][3], long long b[3][3])
{
    long long s;
    int i,j,k;

    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
        {
            for (k=1,s=0;k<=2;k++)
            {
                s=1LL*(s+((1LL*a[i][k]*b[k][j])%md))%md;
            }
            ax[i][j]=s;
        }

    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
            a[i][j]=ax[i][j];

}

void rid(int p)
{
    int i;

    for (i=0;i<=31;i++,inm(a,a))
        if ( (p&(1<<i))==(1<<i))
        {
            inm(sol,a);
        }

}


int main()
{
    f=fopen("kfib.in","r");
    g=fopen("kfib.out","w");

    fscanf(f,"%d",&n);

    if (n<3)
    {
        if (n==0)
            fprintf(g,"0");
        else
            fprintf(g,"1");
        fclose(g);
        return 0;
    }

    rid(n-2);

    solutie=1LL*(sol[1][2]+sol[2][2])%md;
    fprintf(g,"%I64d",solutie);

    fclose(g);
    return 0;
}