#include <stdio.h>

#define mod 666013
typedef int matr[2][2];

matr sol = {{1,1}};

void inmultire(matr a, matr b, matr c)
{
    int i,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]+1LL*a[i][k]*b[k][j])%mod;
}

void calc(int p)///k-1 la apel
{
    int i,j,k;

    matr pow={{0,1},{1,1}};
    for (i=0; (1 << i) <= p; i++)
    {
        if ((p >> i) & 1)
        {
            matr aux={{0,0},{0,0}};
            inmultire(sol,pow,aux);
            for (j=0; j<2 ;j++)
                for (k=0; k<2; k++)
                    sol[j][k]=aux[j][k];
        }
        matr aux={{0,0},{0,0}};
        inmultire(pow,pow,aux);
        for (j=0; j<2; j++)
            for (k=0; k<2; k++)
                pow[j][k]=aux[j][k];
    }
}

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

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

    calc(k-1);
    f=fopen("kfib.out","w");
    fprintf(f,"%d",sol[0][0]);
    fclose(f);
}