#include <stdio.h>

const long long MOD=666013;

long long a[2][2]= {{0,1},{1,1}};
long long an[2][2]= {{0,1},{1,1}};

void matrixmult(long long x[2][2], long long y[2][2], long long z[2][2])
{
    int i,j,k;
    long long m1[2][2];
    long long m2[2][2];

    for (i=0; i<2; i++)
        for (j=0; j<2; j++)
            m1[i][j]=x[i][j];

    for (i=0; i<2; i++)
        for (j=0; j<2; j++)
            m2[i][j]=y[i][j];

    for (i=0; i<2; i++)
        for (j=0; j<2; j++)
            z[i][j]=0;

    for (i=0; i<2; i++)
        for (j=0; j<2; j++)
            for (k=0; k<2; k++)
            {
                z[i][j]=z[i][j]+m1[i][k]*m2[k][j];
                if (z[i][j] > MOD)
                    z[i][j]%=MOD;
            }
}

void pow(int n)
{
    if (n <= 1)
        return;
    if (n%2 == 0)
    {
        pow(n/2);
        matrixmult(an,an,an);
    }
    else
    {
        pow(n-1);
        matrixmult(an,a,an);
    }
}

int main()
{
    FILE *f;
    int k;
    long long ans;

    f=fopen("kfib.in","r");
    fscanf(f,"%d",&k);
    fclose(f);

    f=fopen("kfib.out","w");
    if (k < 2)
        fprintf(f,"1");
    else
    {
        pow(k-2);
        ans=an[0][1]+an[1][1];
        ans%=MOD;
        fprintf(f,"%lld",ans);
    }
    fclose(f);
}